complexity theory NP [duplicate]

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:

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

marked as duplicate by David Richerby, fade2black, Evil, Kyle Jones, Yuval Filmus complexity-theory StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Aug 20 '17 at 10:31

• 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.

So your definition 1 should be read as following

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