0
$\begingroup$

This question already has an answer here:

What is the proof of P ⊆ NP? I cannot happen to find a good explanation for it. I read that the verifier will just ignore the proof and accept any proof if the solution is YES and reject all proofs if the answer is NO. I'm also unclear about verifier.

Definition of P and NP I follow:

P: a problem 'Q' is said to be in P if there exists an efficient (polynomial worst-case time) algorithm for solving the problem. E.g.- "is a given natural number 'x' even?".

NP: a problem 'Q' is said to be in NP if there exists efficient verifiers (an algorithm for verifying if a given proof is correct).

$\endgroup$

marked as duplicate by frafl, Luke Mathieson, Raphael Apr 2 '14 at 15:13

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Heavily depends on your definition of P/NP. Via nondeterministic Turing machines, it's most trivial because any DTM is an NTM with the same time bound. You seem to have some of the witness based definitions, so please explicitly state it. $\endgroup$ – frafl Apr 2 '14 at 13:23
  • $\begingroup$ You have given one of the proofs as part of the question, what part are you having difficulty with? $\endgroup$ – Luke Mathieson Apr 2 '14 at 13:26
  • $\begingroup$ I have included the definition of P and NP that I understand and follow. $\endgroup$ – Harshil Sharma Apr 2 '14 at 13:43
  • $\begingroup$ Now you need to define algorithms. The easiest solution is using a Turing Machine. $\endgroup$ – Виталий Олегович Apr 2 '14 at 13:46
  • $\begingroup$ @VitalijZadneprovskij; a well defined collection of finite steps for accomplishing a task. Also, if you don't mind, could you just post or point me to a proof of P ⊆ NP which I have to understand and explain in a class tomorrow? $\endgroup$ – Harshil Sharma Apr 2 '14 at 13:49
5
$\begingroup$

It's much easier to just define P as the class of languages decided by polynomial-time deterministic Turing machines and NP as the languages decided by polynomial-time nondeterministic Turing machines. Since the deterministic machines are a subset of the nondeterministic ones (the subset that happens to have exactly one option to nondeterministic "choose" from at each step), it's P $\subseteq$ NP is trivial.

If you want to define NP using verifiers, it's not much harder: for a problem in P, the instance is its own certificate. Because you can compute a solution in polynomial time, you can certainly verify whether or not one exists in polynomial time.

$\endgroup$
  • $\begingroup$ So does the verifier doesn't always have to be of the form V(x, y) where 'x' is the original input to the problem and 'y' is a proof? $\endgroup$ – Harshil Sharma Apr 2 '14 at 14:24
  • $\begingroup$ @HarshilSharma the verification process would be as follows: 1. compute a solution from scratch in polynomial time (this is possible by the definition of P). the termination of this computation is another 'proof' - so you just 2. output 'true' without regard to the 'proof' given to you ($y$). $\endgroup$ – collapsar Apr 2 '14 at 14:33
  • $\begingroup$ @HarshilSharma The point is that, if the problem is in polynomial time, you can set $y=x$ (or, actually, anything else). For example, with 3-colouring (NP-complete so probably not in P), $x$ is a graph and $y$ is an assignment of colours; you check whether the assignment is a proper 3-colouring in deterministic polytime. But, for 2-colouring, I can just give you the graph $x$ and you can check in polytime that it's 2-colourable without looking at whatever $y$ you're given. $\endgroup$ – David Richerby Apr 2 '14 at 14:39
  • $\begingroup$ So how can we define a verifier? $\endgroup$ – Harshil Sharma Apr 2 '14 at 14:53
  • $\begingroup$ @HarshilSharma The verifier is the deterministic polynomial-time algorithm that solves the problem for instance $x$, ignoring the certificate $y$. $\endgroup$ – David Richerby Apr 2 '14 at 16:21

Not the answer you're looking for? Browse other questions tagged or ask your own question.