# complexity theory NP [duplicate]

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:

1. Theoretische Informatik; Katrin Erk, Lutz Priese (german)
2. Grundkurs: Theoretische Informatik; Gottfried Vossen, Kurt-Ulrich Witt (german)
3. Theoretische Informatik; Ingo Wegener (german)

And I actually have more links but I can't post them here because I don't have enough reputation

So far I know:

1. A problem L is in NP when there exists a nondeterministic algorithm which solves problem L in polynomial time.
2. 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????????????????

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 !?

• Decision problems can't have approximations as there are only two possibilities: yes or no. There only can be probabilistic algorithms. – rus9384 Aug 19 '17 at 19:05
• Your question is, essentially, "Here are some statements. Do they mean exactly what they say?" Yes, they mean exactly what they say. – David Richerby Aug 19 '17 at 19:10
• Your further thoughts show that you still don't understand the meaning of the basic concepts. I suggest contacting a TA, if available. You can also try our chat. – Yuval Filmus Aug 20 '17 at 15:06

First of all note that a non-deterministic algorithm and a non-deterministic Turing machine are two different things.

A non-deterministic Turing machine is a computational model, while a non-deterministic algorithm "is an algorithm that, even for the same input, can exhibit different behaviors on different runs, as opposed to a deterministic algorithm" (Wikipedia). For example a QuickSort algorithm which partitions the array based on random choice of a pivot is a non-deterministic (probabilistic) algorithm.

A problem $L$ is in $NP$ when there exists a nondeterministic Turing machine which solves problem $L$ in polynomial time.

Similarly, the second definition should be read as following:

NP includes decision problems. If there exists a solution for these problems, it should be possible to check on a deterministic Turing machine in polynomial time whether the solution is indeed a solution.

For the concept of $NP$ see this post.

I think you have misunderstanding with the word 'solution'. It seems that you use it both for an answer to the decision problem and for a certificate that is used in the verification algorithm.

A decision problem is specified by a language $L$, and the problem can be formulated as a question: "Does $L$ contain an input word $w$?"

In the definition of $\operatorname{NP}$ via nondeterministic machines, we consider only this question. If this question can be answered by a polynomial time nondeterministic algorithm, then the language $L$ is in $\operatorname{NP}$.

In the definition that uses verification algorithm, the input to the verification algorithm is different. The (polynomial time) verification algorithm receives the word $w$ and a certificate $z$. If $w$ is contained in $L$, then it should have a certificate (of polynomially bounded length) that the verification algorithm accepts, and if $w$ is not contained in $L$, then there should be no such certificate.

The two definitions are equivalent, because it is possible to guess bits of the certificate using nondeterministic choice, and one can take a sequence of nondeterministic choices that leads to the positive answer as a certificate.

Update:

Consider the TSP problem: Given a weighted graph and a number $k$, does there exist a hamiltonian cycle of weight $\leq k$?

To prove that it is in $\operatorname{NP}$, we can present a poly-time nondeterministic algorithm, which decides this problem. That is, algorithm takes a graph and a number $k$, and if there is a tour of length $\leq k$ in the given graph, then our algorithm has at least one computational path where it answers "yes"; and if there are no short tours, then every path answers "no"

Or we can use a second definition, say that the tour, which we can encode as a sequence of vertices of the graph, is itself a poly-size certificate for its existence. Then we need to present a poly-time deterministic algorithm that takes a graph, a number $k$ and a sequence of vertices and checks if the given sequence defines a tour and the length of this tour is less than $k$.

• Does it matter whether the answer is a 'yes' or a 'no'? Let's take an example because I'm actually trying to understand these classes via the TSP. @Vladimir Lysikov Please take a look at my edited Question – Meliss Aug 20 '17 at 13:06
• @Meliss, every hard problem can either have negative or positive answer. Every problem that is not contained in REG is such a problem. It does not matter what answer is: 0 or 1, NTM can decide both of these cases (in case of TSP or any other problem in NP). – rus9384 Aug 20 '17 at 13:49
• just to be sure: regarding the TSP. If I can say: no a tour like that does not exist! Then the TSP is still in NP? And, do I have to do both: write a nondeterministic algorithm, which calculates a tour <= k in polynomial time and afterwards verify with a deterministic algorithm in polynomial time that the calculated tour is indeed <= k ? Or is just one of these enough? @rus9384 – Meliss Aug 20 '17 at 14:04
• @Meliss, I edited the answer to include the TSP example. – Vladimir Lysikov Aug 20 '17 at 14:22
• To your first definition: so we let the algorithm run many times and if there is at least one cycle of weight <= k , then the answer is yes --> implies that TSP is in NP -- if there are none cycles of weight <= k, then the answer is no --> does is still imply that tsp is in NP @VladimirLysikov – Meliss Aug 20 '17 at 14:37