Valiant–Vazirani theorem (original) (raw)
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 proof is based on the Mulmuley–Vazirani–Vazirani isolation lemma, which was subsequently used for a number of important applications in theoretical computer science.
| Property | Value |
|---|---|
| dbo:abstract | 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 proof is based on the Mulmuley–Vazirani–Vazirani isolation lemma, which was subsequently used for a number of important applications in theoretical computer science. 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 satisfying assignment. (en) O Teorema de Valiant–Vazirani é um teorema na teoria da complexidade computacional. Foi provado por Leslie Valiant e Vijay Vazirani em um artigo intitulado "NP is as easy as detecting unique solutions", publicado em 1986.O teorema afirma que, se existe um algoritmo de tempo polinomial para SAT-não-ambíguo, então NP=RP.A prova é baseada no lema do isolamento de Mulmuley–Vazirani–Vazirani , que, posteriormente, foi utilizado por uma grande quantidade de aplicações na teoria da ciência da computação. O teorema de Valiant–Vazirani implica que o Problema da satisfatibilidade booleana, que é NP-completo, continua a ser um problema computacionalmente difícil mesmo se as instâncias de entrada são forçadas a ter no máximo uma atribuição satisfeitora. (pt) |
| dbo:wikiPageID | 3003434 (xsd:integer) |
| dbo:wikiPageLength | 4285 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1123699119 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:NP_(complexity) dbr:Nondeterministic_Turing_machine dbr:NP-complete dbc:Structural_complexity_theory dbr:Leslie_Valiant dbc:Theorems_in_computational_complexity_theory dbr:Computational_complexity_theory dbr:P_(complexity) dbr:Theoretical_computer_science dbr:Promise_problem dbr:Isolation_lemma dbr:Boolean_satisfiability_problem dbr:RP_(complexity) dbr:UP_(complexity) dbr:Vijay_Vazirani |
| dbp:wikiPageUsesTemplate | dbt:Reflist dbt:Short_description |
| dcterms:subject | dbc:Structural_complexity_theory dbc:Theorems_in_computational_complexity_theory |
| gold:hypernym | dbr:Theorem |
| rdf:type | yago:WikicatTheoremsInComputationalComplexityTheory yago:Abstraction100002137 yago:Communication100033020 yago:Message106598915 yago:Proposition106750804 yago:Statement106722453 yago:Theorem106752293 |
| rdfs:comment | 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 proof is based on the Mulmuley–Vazirani–Vazirani isolation lemma, which was subsequently used for a number of important applications in theoretical computer science. (en) O Teorema de Valiant–Vazirani é um teorema na teoria da complexidade computacional. Foi provado por Leslie Valiant e Vijay Vazirani em um artigo intitulado "NP is as easy as detecting unique solutions", publicado em 1986.O teorema afirma que, se existe um algoritmo de tempo polinomial para SAT-não-ambíguo, então NP=RP.A prova é baseada no lema do isolamento de Mulmuley–Vazirani–Vazirani , que, posteriormente, foi utilizado por uma grande quantidade de aplicações na teoria da ciência da computação. (pt) |
| rdfs:label | Teorema de Valiant-Vazirani (pt) Valiant–Vazirani theorem (en) |
| owl:sameAs | freebase:Valiant–Vazirani theorem wikidata:Valiant–Vazirani theorem dbpedia-pt:Valiant–Vazirani theorem https://global.dbpedia.org/id/4x2fn |
| prov:wasDerivedFrom | wikipedia-en:Valiant–Vazirani_theorem?oldid=1123699119&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Valiant–Vazirani_theorem |
| is dbo:knownFor of | dbr:Leslie_Valiant__Leslie_Valiant__1 dbr:Vijay_Vazirani |
| is dbo:wikiPageRedirects of | dbr:Valiant-Vazirani_Theorem dbr:Valiant-Vazirani_theorem |
| is dbo:wikiPageWikiLink of | dbr:Leslie_Valiant dbr:Isolation_lemma dbr:Toda's_theorem dbr:UP_(complexity) dbr:Vijay_Vazirani dbr:List_of_theorems dbr:NP-completeness dbr:Structural_complexity_theory dbr:Valiant-Vazirani_Theorem dbr:Valiant-Vazirani_theorem |
| is dbp:knownFor of | dbr:Vijay_Vazirani |
| is foaf:primaryTopic of | wikipedia-en:Valiant–Vazirani_theorem |