Don't understand why (a) is not a solution for check-in 14.1. Consider the NTM which decides whether \in HAMPATH or not. NTM *decides* this in poly(m) time, where m = size of input (say, the number of vertices). Thus, NTM is able to accept or reject input in poly (m). Since it is also able to reject in poly(m) time, why can't you invert the solution? Or am I wrong in believing that it can also reject in poly(m) time?
The only way I see of resolving the above is that if x otin L, is not (known) to be proved in poly time by an NTM. Only when x \in L, then an NTM can prove it to be so in poly time.
I think it has to do with NDTMs being asymmetrical. They accept if any path accepts even if all the others reject. They reject only if no path accepts. Example: Suppose an NDTM has 2 accept paths and 2 reject paths on some string w. If we invert the accept and reject states then it would still accept. We would want it to reject. Its all about the definition of NDTM acceptance Hope this helps.
My guess is that the operation of “inversion” requires checking all the branches and confirm they are all rejection, which is not polynomial time. There is no explicit way to make a NDTM to directly output accept for the HAMPATH complement, even though output reject is easy, it doesn’t fit the definition of “accept the language”
I think it is because NTM's parallel computation branches cannot communicate with each other, they represent parallel branches of computation like copies of the machine themselves so the copies can't share information because that's not what non determinism enclose so in order to check ~HAMPATH we would need to collect the results of the HAMPATH NTM and check them but it's not possible to do that that's not how the TM for HAMPATH works, TM for HAMPATH just accepts if any of the branches find a Hamiltonian path they don't care about other computations it's because they can't, they can't interact with other branches they are doing their own computation and either they succeed or fail
If I understood correctly I think testing doesn't need verification of a "short certificate", in other words verifying is checking one possible branch only (in P time) in the case of nondeterministic
To me test and verify are almost synonyms. I think a better term would be: P = easy to compute / calculate NP = easy to verify (as in, is the result of this calculation valid or not)
Why do we say that for a NTM decider, all branches halt on all inputs? By "branches halt" do we include the possibility of one of the branches having an accepting state and hence all the other branches halt when we find that accepting state? (Since if the NTM finds an accepting state it halts).
One consequence of that definition would be that not every NTM "decider" could be converted to an equivalent DTM decider, because on certain inputs not in the NTM's language (i.e. those with no accepting branch in the NTM), the DTM would have to simulate infinite branches of the NTM, and we would never be sure if the NTM was looping forever or just hadn't accepted yet. So it would be an unnatural definition in that sense.
I think it just means that the language of such an NTM has to be decidable because it's a "decider" so it can't have undecidability in its language, It's not an *recognizer* it's a *decider* and each branch of computation runs in parallel there's no communication between nondeterministic branches so they all must halt now taking HAMPATH example: Even if one of the branches halts in the accept state then we found a path otherwise we didn't
It is a very good series of videos, but it has a caveat. Professor Sipster seems to try to explain in detail without first giving a definite answer....
@@subhamjyoti1129 It's not correct to say that there are "many" black computer scientists, there are not enough black computer scientists or women, it's a fact.
![Six Hundred Strike [EPIC: The Musical] Full Animatic](http://i.ytimg.com/vi/zov6NXIAuow/mqdefault.jpg)
*There is no video for Lecture 13 as that was the day for the Midterm Exam.*
29:10 Here's the paper covering the proof for anyone wondering:- www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf
Don't understand why (a) is not a solution for check-in 14.1.
Consider the NTM which decides whether \in HAMPATH or not.
NTM *decides* this in poly(m) time, where m = size of input (say, the number of vertices).
Thus, NTM is able to accept or reject input in poly (m).
Since it is also able to reject in poly(m) time, why can't you invert the solution?
Or am I wrong in believing that it can also reject in poly(m) time?
The only way I see of resolving the above is that if x
otin L, is not (known) to be proved in poly time by an NTM.
Only when x \in L, then an NTM can prove it to be so in poly time.
I think it has to do with NDTMs being asymmetrical. They accept if any path accepts even if all the others reject. They reject only if no path accepts.
Example:
Suppose an NDTM has 2 accept paths and 2 reject paths on some string w. If we invert the accept and reject states then it would still accept. We would want it to reject.
Its all about the definition of NDTM acceptance
Hope this helps.
@@austinoquinn815 yea, I now know what you say to be true.
My guess is that the operation of “inversion” requires checking all the branches and confirm they are all rejection, which is not polynomial time. There is no explicit way to make a NDTM to directly output accept for the HAMPATH complement, even though output reject is easy, it doesn’t fit the definition of “accept the language”
I think it is because NTM's parallel computation branches cannot communicate with each other, they represent parallel branches of computation like copies of the machine themselves so the copies can't share information because that's not what non determinism enclose so in order to check ~HAMPATH we would need to collect the results of the HAMPATH NTM and check them but it's not possible to do that that's not how the TM for HAMPATH works, TM for HAMPATH just accepts if any of the branches find a Hamiltonian path they don't care about other computations it's because they can't, they can't interact with other branches they are doing their own computation and either they succeed or fail
What is the difference between "testing" and "verifying"?
If I understood correctly I think testing doesn't need verification of a "short certificate", in other words verifying is checking one possible branch only (in P time) in the case of nondeterministic
To me test and verify are almost synonyms. I think a better term would be:
P = easy to compute / calculate
NP = easy to verify (as in, is the result of this calculation valid or not)
Why do we say that for a NTM decider, all branches halt on all inputs?
By "branches halt" do we include the possibility of one of the branches having an accepting state and hence all the other branches halt when we find that accepting state? (Since if the NTM finds an accepting state it halts).
One consequence of that definition would be that not every NTM "decider" could be converted to an equivalent DTM decider, because on certain inputs not in the NTM's language (i.e. those with no accepting branch in the NTM), the DTM would have to simulate infinite branches of the NTM, and we would never be sure if the NTM was looping forever or just hadn't accepted yet. So it would be an unnatural definition in that sense.
I think it just means that the language of such an NTM has to be decidable because it's a "decider" so it can't have undecidability in its language, It's not an *recognizer* it's a *decider* and each branch of computation runs in parallel there's no communication between nondeterministic branches so they all must halt now taking HAMPATH example: Even if one of the branches halts in the accept state then we found a path otherwise we didn't
where is vid number 13 btw?
There is no video for Lecture 13 as that was the day for the Midterm Exam.
proud to be IIT-ian
It is a very good series of videos, but it has a caveat. Professor Sipster seems to try to explain in detail without first giving a definite answer....
Why aren't there black cs professors?
ruclips.net/video/yzMVEbs8Zz0/видео.html He is tho?
there are many , for instance, Jelani Nelson(great teacher)
if you're looking for black people in cs, amigoscode gives amazing lectures. technically not a professor but hes a fantastic educator on youtube :)
@@subhamjyoti1129 It's not correct to say that there are "many" black computer scientists, there are not enough black computer scientists or women, it's a fact.
what's the point of this question under this specific video?