Pop Quiz #3

If two graphs have different drawings, they are not isomorphic.

A graph isomorphism is a 1-to-1 mapping of the edge set.

For an interactive proof system to fulfill the completeness requirement, there must be a proof such that the verifier will accept with probability at least 99%.

The soundness property of interactive proof systems requires that there is a proof such that the verifier will not accept.

Every language in P has an interactive proof system.

In an interactive proof system, the prover must not exceed polynomial time.

In an interactive proof system, the verifier cannot exceed polynomial memory.

In zero-knowledge interactive proof systems, the prover may not gain any knowledge.

If no knowledge was gained, the protocol can be simulated with just one party by a non-interactive machine in polynomial time.

There is a zero-knowledge interactive proof system for the "k-clique" language (the set of all graphs that contain cliques of size at least k, where a clique is a fully connected sub-graph).

Bit commitment is a two-party two-phase protocol.

The hiding property of the bit commitment scheme states that the receiver cannot determine the committed value noticeably better than by guessing.

If there are one-way functions, there are bit commitment schemes.

If there are one-way permutations, there are bit commitment schemes.

The language of all prime numbers is Karp-reducible to SAT, the language of all satisfiable Boolean formulae.