Write, autoreview, editor, reviewer
3,129
edits
Verification of NP-complete problems: Difference between revisions
Jump to navigation
Jump to search
no edit summary
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
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> | 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 [[ | 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. | '''Tags:''' Verification, Quantum Advantage, Communication Complexity, QMA, BQP, NP-complete, unentanglement. | ||