Primality is the following problem :
Given a positive integer $n$, is $n$ prime ?
Note that the size of the input is the number of bits used to represent $n$.
Easy : Show that Primality is in co-NP
Show that Primality is in NP
Hence conclude that Primality is in NP $\cap$ co-NP.
Do not use the Primality is in P theorem.
Posted: Jun 19 '12
Seen: 76 times
Last updated: Jun 19 '12
