1
$\begingroup$

I have an assignment in which the problem, $D$, is simple but, once found, easy to check. Is it enough to prove that a solution $x$ can be checked in polynomial time to prove that $D \in NP$? (The problem $D$ is a decision problem)

Edit: Changed $P$ to $D$

$\endgroup$
4
$\begingroup$

The two requirements for a problem to be in NP are

  1. it must be possible to check a given solution in polynomial time;
  2. there must be some polynomial $f$ such that solutions to instances of length $n$ have size at most $f(n)$.

Properly, the "solutions" are referred to as "certificates" since they don't have to be an actual solution to the problem. Normally, the certificate to something like a satisfiability problem would be a satisfying truth assignment, but anything that "proves" the instance is in the langauge is acceptable. In particular, the proof that every language in NP can be thought of in these terms uses a description of the accepting computation of a Turing machine as the certificate.

This gives intuition why the certificate has to have polynomial length: the Turing machine was only allowed to run for a polynomial number of steps. Indeed, if you dropped the polynomial length requirement on the certificate, even the halting problem would "be in NP". The certificate would be a description of the steps taken by the Turing machine before it halts; you can easily check in polynomial time that a certificate is valid, but the certificate itself might have arbitrary length.

$\endgroup$
  • $\begingroup$ Thank you! Okay so f(n) will work as a kind of upper bound to the length of the solutions? Is there any systematic way to find such a polynomial function or prove that there is one? $\endgroup$ – Nyfiken Gul Feb 23 '17 at 17:56
  • $\begingroup$ @NyfikenGul Yes, it will. But there's no systematic way of finding what $f$ is. Mathematical proof is a creative act, not a mechanical process. $\endgroup$ – David Richerby Feb 23 '17 at 19:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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