| 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
| |
| dbo:wikiPageLength
|
- 4285 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| 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
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:knownFor
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is dbp:knownFor
of | |
| is foaf:primaryTopic
of | |
