This question already has an answer here:
Ok, I really need help because I have read in so many books but still don't understand the complexity class NP.
These are the books:
- Theoretische Informatik; Katrin Erk, Lutz Priese (german)
- Grundkurs: Theoretische Informatik; Gottfried Vossen, Kurt-Ulrich Witt (german)
- Theoretische Informatik; Ingo Wegener (german)
- https://de.wikipedia.org/wiki/NP_(Komplexitätsklasse) (german)
- https://www.ibm.com/developerworks/community/blogs/jfp/entry/no_the_tsp_isn_t_np_complete?lang=en (english)
And I actually have more links but I can't post them here because I don't have enough reputation
So far I know:
- A problem L is in NP when there exists a nondeterministic algorithm which solves problem L in polynomial time.
- NP includes decision problems. If there exists a solution for these problems, it should be possible to check with a deterministic algorithm in polynomial time whether the solution is indeed a solution.
To 1.: is the calculated solution an exact match or is it just an approximation? To 2.: is it just necessary to be able to check in polynomial time? For example: the solution is not indeed a solution but I was able to check it in polynomial time. Is the problem still in NP?
For a problem to be in NP, I must have a nondeterministic algorithm which solves the problem in polynomial time. The solution is an exact match and I must be able to check in polynomial time with an deterministic algorithm that the solution is indeed a solution????????????????
Can someone please help me to understand.
Further thoughts: Let's take the TSP as an example. Question: Does a tour exist <= k ?
Let's assume I wrote a nondeterministic algorithm, which calculates a tour <= k. So my answer would be: Yes, a tour like that exists.
However Vladimir wrote in his answer: If this question can be answered by a polynomial time nondeterministic algorithm, then the language L is in NP.
So I gave an answer 'yes'; that means the TSP is in NP?! However what about if my answer would be: No, a tour like that does not exist! ? Then the TSP would not be in NP?
And looking on the other definition: Further I answered: Yes, a tour like that exists, because my nondeterministic algorithm calculated a tour like that. Now if I can check with a deterministic algorithm in polynomial time that the calculated tour is indeed verified to be correct, then TSP is in NP !?