Editing Verification of NP-complete problems (section)

The aim of the protocol is to verify NP-complete problems in the context of [[communication complexity]], so in the case in which the amount of communication between the involved parties is a resource. By definition, if a problem is in NP then it is possible to verify efficiently if a given solution is correct. However, if the given solution, or [[witness]], is incomplete then the verification process is exponential in the size of the missing information.</br>
In this setting, Merlin,  an overpowerful but untrusted prover, wants to convince Arthur, a honest but computationally bounded verifier, that he has the solution to a specific NP-complete problem. It was shown by [[Verification of NP-complete problems#References|ADS (2008)]] that if Merlin sends quantum proofs revealing only partial information about the complete solution, Arthur can efficiently verify it in a probabilistic sense, giving rise to a computational advantage with no analogous in the classical world. These quantum class of problems is called QMA, as in Quantum Merlin Arthur, and is the generalization of NP problems as it consists to the class of languages that can be verified efficiently with quantum proofs.</br>

'''Tags:''' Verification, Quantum Advantage, Communication Complexity, QMA, BQP, NP-complete, unentanglement.