How to show that problems are in NP?

Question

I want to show that the following problems are in NP (NP-completeness is irrelevant) by textually describing a non-deterministic Turing machine which runs in polynomial time. The assumptions are that addition, multiplication, tests for divisibility can be done in polynomial time and natural numbers are represented in binary.

a) $\{n \in \mathrm{N} \ | \ n \ $is not a prime number$\}$

b) $\{x_1, ..., x_n, y \in \mathrm{N} \ | \exists M \subseteq \{1, ..., n\} : \sum_{m \in M}x_m = y \ \}$

For a) it's clear that there must be a non-trivial divisor if $n$ isn't a prime, but how does it exactly work? How can I reject invalid and verify valid inputs?

Answer 1

The easiest way to prove some problem is in $\mathsf{NP}$ is using the certificate definiiton of $\mathsf{NP}$ mentioned in other answers. The nondeterministic definition of $\mathsf{NP}$ is usually not very useful for showing a problem belongs to $\mathsf{NP}$. Intuitively, a problem is in $\mathsf{NP}$ iff we have an efficient (polynomial time) verification algorithm with polynomial size certificates/proofs.

For example, if you want to check if a given number $m$ is composite, the following works:

• Format of certificates: certificates are a pair numbers $(a, b)$,
• Verification algorithm: a certificate $(a,b)$ is accepted iff $1<a,b<m$ and $ab=m$.

If a number is composite then there is a pair of number $(a,b)$ which satisfies the condition and has size $O(\lg m)$. It is important that the certificate has polynomial size in the size of input (here the size of input is $\lg m$).

If a number is not composite there are no such pairs.

Note that we fix a particular certificate verifier for all inputs. You cannot change the verification algorithm from one input to another one.

A more challenging question is to show that primeness is also in $\mathsf{NP}$, i.e. there are polynomial size primality certificates.

Answer 2

In order to show that problem 1 is in NP, we follow your advice and use the fact that a number is not prime iff it has a non-trivial divisor. Problems in NP have an algorithm which accepts a "proof" that the input belongs to the language. These algorithms must satisfy two properties:

1. Every $x \in L$ has some proof $\pi$.
2. No $x \notin L$ has any proof $\pi$.

In addition, $\pi$ needs to be polynomial size, and the algorithm verifying the proof must run in polynomial time. The maximal size of the proof $\pi$ needs to be fixed in advance.

For your example, the proof $\pi$ is a non-trivial factor of the input $x$. Let's check all the requisite properties:

1. If $x \in L$ then $x$ is not a prime and so has a non-trivial factor $\pi$.
2. If $x \notin L$ then $x$ is prime and so it doesn't have any non-trivial factors.
3. The size of a non-trivial factor is at most the size of $x$, and so we can bound the size of $\pi$ by the size of $x$ (which is polynomial size).
4. Verifying that $\pi$ is a non-trivial factor of $x$ can be done in polynomial time, since division takes polynomial time.

As a side remark, it is now known that primality testing is in P, and so the language in question actually has a polynomial time algorithm. This means that we can dispense with the proof $\pi$.