Valiant–Vazirani theorem
id:
valiant-vazirani-theorem-284-15427038
title:
Valiant–Vazirani theorem
text:
The Valiant–Vazirani theorem is a theorem in computational complexity theory stating that if there is a polynomial time algorithm for Unambiguous-SAT, then NP = RP. It was proven by Leslie Valiant and Vijay Vazirani in their paper titled NP is as easy as detecting unique solutions published in 1986. The Valiant–Vazirani theorem implies that the Boolean satisfiability problem, which is NP-complete, remains a computationally hard problem even if the input instances are promised to have at most one
brand slug:
wiki
category slug:
encyclopedia
description:
If there is a polynomial time algorithm for unambiguous-SAT, then NP equals RP
original url:
https://en.wikipedia.org/wiki/Valiant%E2%80%93Vazirani_theorem
date created:
date modified:
2023-12-04T15:09:52Z
main entity:
{"identifier":"Q7911648","url":"https://www.wikidata.org/entity/Q7911648"}
image:
fields total:
13
integrity:
14