Interactive Proof Systems
Interactive Proof Systems
- Using algebraic structure of NP, I can convince you that a graph is not three colorable by having you ask me random questions.
- Similar techniques can be used to produce quickly verifiable proofs.
- Lower bound of ne for graph coloring unless P = NP.