CS502 current GDB solution
Tuesday, July 05, 2011 Posted In CS and IT Edit ThisDear Students! Your GDB will be conducted on 5th July to 6th July 2011 be ready to post your comments on these specified days topic is given below :
“NP complete problems are solvable /decidable problems.” Support or contradict the statement with solid arguments with respect to time constraints. Only two to three sentences are required to give the complete idea.
Guidelines:
Brief answer with solid arguments is the requirement for good grading .Your comments should be in your own words; in case of cheating or making copy of other students will be graded as zero.
please Discuss
SOLUTION:
I happen to know that anything problem that can be decided by a non-deterministic turing machine can also be decided by a turing machine (just slower), so NP problems should be all decidable.
:::::::::::::::::::::::::::::::::
Not a computer scientist, but doesn't being NP mean that the problem is decidable in polynomial time, on a non-deterministic turing machine? I happen to know that anything problem that can be decided by a non-deterministic turing machine can also be decided by a turing machine (just slower), so NP problems should be all decidable.
