What is the definition of class CoNP?
What is the definition of class PSPACE?
Are there any problems that are PSPACE-COMPLETE? If so, name one.
Are there any problems that are CoNP-COMPLETE? If so, name one.
NPSPACE is a nondeterministic analog of PSPACE. Are PSPACE and NPSPACE different? What is known about that?
DP is a complexity class that lies between NP and PSPACE. That is, NP is a subset of DP and DP is a subset of PSPACE. DP-complete problems are defined in the usual way for classes in this region of complexity. What is the definition of a DP-complete problem?
It is not known whether or not CoNP and NP are the same classes of problems. Show that, if NP and CoNP are different, then P and NP are also different. (Hint: Suppose that NP and CoNP are different. Reason that P and NP must also be different by contradiction. Notice that P is closed under complementation. That is, if X ∈ P then X ∈ P.) Give a clearly reasoned proof, not just a rehash of the hints.
Does 4 have an inverse mod 9? That is, does there exist an integer x such that 4x = 1 (mod 9)? If so, what is x? If not, why not?
Does 6 have an inverse mod 9? That is, does there exist an integer x such that 6x = 1 (mod 9)? If so, what is x? If not, why not?
What is the discrete square root problem? Describe the input and the output. Give an example.
Computing discrete square roots mod n, where n is the product of two primes, is, in some sense, as hard as factoring n. What mechanism is used to show that? In what sense is computing discrete square roots as hard as factoring?
If primes p = 5 and q = 11 are chosen, what are the private and public keys selected for the RSA system? What are the encoding and decoding functions?
In public key cryptography, we give away enough information to break the encryption. What makes us think that nobody can make effective use of that information?