0
$\begingroup$

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

Improve this question
$\endgroup$
5
  • $\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, 2014 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, 2014 at 13:26
  • $\begingroup$ I have included the definition of P and NP that I understand and follow. $\endgroup$
    – Harshil Sharma
    Apr 2, 2014 at 13:43
  • $\begingroup$ Now you need to define algorithms. The easiest solution is using a Turing Machine. $\endgroup$
    – Vitaly Olegovitch
    Apr 2, 2014 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, 2014 at 13:49

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
7
  • $\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, 2014 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, 2014 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, 2014 at 14:39
  • $\begingroup$ So how can we define a verifier? $\endgroup$
    – Harshil Sharma
    Apr 2, 2014 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, 2014 at 16:21

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