Easy proof for $Primes \in NP$

I want to show that $Primes \in NP$ an I've seen multiple proofs that use facts from number theory, like this one.

But isn't it much easier to proof
$$Composites=\{x\in \mathbb{N}\cup\{0\}:x=1 \vee\exists p,q>1: x=pq\} \in NP$$
first and then doing a polynomial reduction on $Primes$?

Because I can make a simple Turin-Machine Verifier that goes like this...

TM M on input $(n, (p,q))$

• Check if $1

• Check if $n=1$ or $n=pq$

• Check if $n\geq 1$

• If all the checks above are true, then accept. Else decline.

All the number specifications are clearly polynomial, multiplication is also polynomial $\Rightarrow Composites \in NP$

Now I want to find a polynomial reduction i.e. $Primes \leq_p Composites$

Clearly, $\overline{Primes}=Composites$, so we have $n \in Primes \Leftrightarrow n\notin Composites$

I define the function (Turing-Machine) $N$ on input $n$ simply as: If $n\in Primes$, decline. Else accept. (This TM runs in constant time)

Then, $n \in Primes \Leftrightarrow N(n) \in Composites$

Since $Primes \leq_p Composites$ and $Composites\in NP$ $\Rightarrow Primes\in NP$

Here is the definition of NP:

A language $L$ is in NP if there is a polytime machine $T$ and a polynomial $p$ such that:

• If $x \in L$ then there exists $y$ of size at most $p(|x|)$ such that $T(x,y) = 1$.

• If $x \notin L$ then for all $y$ of size at most $p(|x|)$, $T(x,y) = 0$.

We think of $y$ as a witness.

Composites is in NP since $y$ could be a nontrivial factorization of $x$, and $T$ just checks that $y$ is indeed a factorization of $x$. Let $p$ be a polynomial such that there is always a factorization of size at most $p(|x|)$.

You're suggesting to define $S(x,y) = 1 - T(x,y)$. Let's see what this $S$ satisfies:

• If $x$ is prime then for all $y$ of size at most $p(|x|)$, $T(x,y) = 1$.

• If $x$ is composite then there exists $y$ of size at most $p(|x|)$ such that $T(x,y) = 0$.

This is not quite what we want in the definition of NP. In fact, the language that $S$ accepts nondeterministically is probably $\Sigma^*$, since for every $x$ we can find a non-factorization $y$.

StackExchange Computer Science Q#141074, answer score: 3