# Proving the language of non-primes is in NP

Computer Science Asked by builderthebob00 on February 6, 2021

I am learning about NP problems and found this problem in my textbook that I was not sure how to answer, and was looking for some help on how to start the question.

Show the following language is in NP:

Not-Prime = {n ∈ N: n is not a prime number}

So far, I have created an efficient decider for the language with a certificate, but I’m not sure how to prove that the language is actually in NP. Thank you for any advice!

If you created a deterministic polynomial-time algorithm $$A$$ that can check a "yes"-certificate for Not-Prime (of polynomial length in the size of instance), then you already proved that your problem is in $$mathsf{NP}$$.

Say that a polynomial upper bound on the length of the certificate is $$p(s)$$, where $$s$$ is the size of the instance. A non-deterministic polynomial-time algorithm for Not-Prime can do the following:

• Guess the length $$ell$$ of the certificate in $${0, dots, p(s)}$$.
• For $$i=1, dots, ell$$: guess the $$i$$-th bit $$c_i$$ of the certificate.
• Run $$A$$ on the certificate $$c_1 c_2 dots c_ell$$. If $$A$$ accepts, accept. Otherwise reject.

A certificate for an instance $$n$$ of Not-Prime is just a non-trivial prime factor of $$n$$ (which requires at most $$lceil log n rceil$$ bits to be represented, so you can pick $$p(s)=s$$).

Answered by Steven on February 6, 2021

## Related Questions

### DFA for every run of a’s=2 or 3

3  Asked on December 17, 2021 by matt-mowris

### Is there a way to determine whether a list of integers can be a prefix function?

1  Asked on December 17, 2021 by mchl

### ‘Half-Close’ figure of Data Communications and Networking, 5/e

1  Asked on December 14, 2021

### Proof that $L={a^ncb^n| n in mathbb{N}}$ is not regular

2  Asked on December 14, 2021

### Merge two sorted arrays without using additional memory

1  Asked on December 10, 2021 by guy-kahlon

### Uniform generation of random bipartite bi-regular graphs?

2  Asked on December 10, 2021

### How to solve recursion with two separate converges rates

1  Asked on December 10, 2021 by ofir-gordon

### Context free languages invariant by “shuffling” right hand side

1  Asked on December 10, 2021 by vor

### Object algebras without anonymous inner classes

0  Asked on December 10, 2021 by byteeater

### Does $20n$ belong to $O(n^{1-epsilon})$ for some $epsilon > 0$?

1  Asked on December 7, 2021

### Bit times and propagation delay

1  Asked on December 6, 2021 by brazen

### Enumerate all valid orders of subset sums

1  Asked on December 6, 2021 by xskxzr

### “Knapsack problem” with repetition, “lesser or equal” constraint, and recording all valid combinations

1  Asked on December 6, 2021

### How do compilers assure stability?

4  Asked on December 4, 2021

### If we prove that there is an NP-complete problem that is P, Can we consider that P=NP?

2  Asked on December 4, 2021 by mwit30-room8

### Is it possible to uniformly shuffle N items into a deque of size N where you can only modify the first or last elements?

1  Asked on December 4, 2021

### Spanning tree in a graph of intersecting sets

2  Asked on December 4, 2021

### Is the two-color leapfrog problem in P?

0  Asked on December 2, 2021

### Problem with proving that $RP subseteq NP$ : a non-deterministic TM for a language $L in RP$

1  Asked on November 30, 2021 by pedro-costa

### A monad is just a monoid in the category of endofunctors, what’s the enlightenment?

1  Asked on November 30, 2021