Suggest a Book

Primality is in NP $\cap$ co-NP

Level: unknown

posted Jun 19 '12

Shiva Kintali
691 1 6 22
http://www.cs.princeton.e...

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.

delete retag edit

Stats

Posted: Jun 19 '12

Seen: 76 times

Last updated: Jun 19 '12