Editing Verification of NP-complete problems (section)

==Properties==
The protocol
* involves two parties and one-way communication from the prover to the verifier.
* assumes that anyone might be dishonest and still provide perfect completeness and constant soundness.
* has a communication complexity of <math>O(\sqrt{N}\log_2N)</math> bits of information.
* runs in exponential time, while it can be shown that by using classical proofs, the best protocol run in exponential time in the size of N.
* can be implemented with linear optics (not exclusively).
* It has been theorized that N needs to be at least about 500 in order to have the advantage over the best classical protocol.