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

3 Asked on February 21, 2021 by always-newbie

1 Asked on February 20, 2021 by saku

1 Asked on February 20, 2021 by rossko_dca

1 Asked on February 17, 2021 by donvitomarco

0 Asked on February 16, 2021 by von-spotz

0 Asked on February 13, 2021 by adam-cole

a star search algorithms euclidean distance graphs shortest path

1 Asked on February 13, 2021 by aviv-barel

5 Asked on February 10, 2021 by gizmo

0 Asked on February 10, 2021 by arthur-b

1 Asked on February 8, 2021 by keith-paton

1 Asked on February 7, 2021 by user3661613

1 Asked on February 6, 2021 by builderthebob00

0 Asked on February 5, 2021 by pookie

1 Asked on February 4, 2021 by retsek680

1 Asked on February 3, 2021 by stark2022

0 Asked on February 1, 2021 by david-grnberger

0 Asked on January 30, 2021 by tzlil

0 Asked on January 29, 2021 by angelic-demonic

Get help from others!

Recent Questions

- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?
- Does Google Analytics track 404 page responses as valid page views?

Recent Answers

- Peter Machado on Why fry rice before boiling?
- Joshua Engel on Why fry rice before boiling?
- haakon.io on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?

© 2023 AnswerBun.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP