Write
262
edits
Verification of NP-complete problems: Difference between revisions
Jump to navigation
Jump to search
→Assumptions
| Line 6: | Line 6: | ||
==Assumptions== | ==Assumptions== | ||
* The problem must be a ''[[balanced formula]]'', meaning that every variable occurs in at most a constant number of clauses; | * The problem must be a ''[[balanced formula]]'', meaning that every variable occurs in at most a constant number of clauses; | ||
* It must be a [[PCP]], i.e. either the formula is satisfiable, or at least a fraction of the clauses must be unsatisfiable; | |||
be unsatisfiable; | *''Exponential time hypothesis'', i.e. any NP-complete problem cannot be solved in sub-exponential time in the worst case. | ||
*''Exponential time hypothesis'', i.e. any NP-complete problem cannot be solved in | |||
* There is a promise of no [[entanglement]] between the quantum proofs. | * There is a promise of no [[entanglement]] between the quantum proofs. | ||
The first two conditions are always met when reducing the NP problem to a [[3SAT]] and then to a [[2-out-of-4SAT]]. The exponential hypothesis is unproven but very accredited conjecture which implies that <math>P\neq NP</math>. The [[un-entanglement]] promise is typical in these scenarios as it was proved that Merlin can always cheat by entangling the proofs and there is no way for Arthur to verify | The first two conditions are always met when reducing the NP problem to a [[3SAT]] and then to a [[2-out-of-4SAT]]. The exponential hypothesis is unproven but very accredited conjecture which implies that <math>P\neq NP</math>. The [[un-entanglement]] promise is typical in these scenarios as it was proved that Merlin can always cheat by entangling the proofs and there is no way for Arthur to verify state by pre-preparing the ancillary states with special coefficients. | ||
==Outline== | ==Outline== | ||