This HTML5 document contains 58 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n15https://global.dbpedia.org/id/
yagohttp://dbpedia.org/class/yago/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
dbpedia-pthttp://pt.dbpedia.org/resource/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
wikipedia-enhttp://en.wikipedia.org/wiki/
dbphttp://dbpedia.org/property/
dbchttp://dbpedia.org/resource/Category:
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
goldhttp://purl.org/linguistics/gold/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:Leslie_Valiant__Leslie_Valiant__1
dbo:knownFor
dbr:Valiant–Vazirani_theorem
Subject Item
dbr:Valiant–Vazirani_theorem
rdf:type
yago:WikicatTheoremsInComputationalComplexityTheory yago:Statement106722453 yago:Abstraction100002137 yago:Message106598915 yago:Communication100033020 yago:Proposition106750804 yago:Theorem106752293
rdfs:label
Teorema de Valiant-Vazirani Valiant–Vazirani theorem
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. 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.
dcterms:subject
dbc:Theorems_in_computational_complexity_theory dbc:Structural_complexity_theory
dbo:wikiPageID
3003434
dbo:wikiPageRevisionID
1123699119
dbo:wikiPageWikiLink
dbr:Computational_complexity_theory dbr:Nondeterministic_Turing_machine dbr:NP-complete dbr:UP_(complexity) dbr:Boolean_satisfiability_problem dbr:Leslie_Valiant dbc:Theorems_in_computational_complexity_theory dbr:Isolation_lemma dbr:Theoretical_computer_science dbr:NP_(complexity) dbr:RP_(complexity) dbr:Vijay_Vazirani dbr:P_(complexity) dbr:Promise_problem dbc:Structural_complexity_theory
owl:sameAs
wikidata:Q7911648 dbpedia-pt:Teorema_de_Valiant-Vazirani n15:4x2fn freebase:m.08jyrl
dbp:wikiPageUsesTemplate
dbt:Reflist dbt:Short_description
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. 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.
gold:hypernym
dbr:Theorem
prov:wasDerivedFrom
wikipedia-en:Valiant–Vazirani_theorem?oldid=1123699119&ns=0
dbo:wikiPageLength
4285
foaf:isPrimaryTopicOf
wikipedia-en:Valiant–Vazirani_theorem
Subject Item
dbr:Leslie_Valiant
dbo:wikiPageWikiLink
dbr:Valiant–Vazirani_theorem
Subject Item
dbr:Isolation_lemma
dbo:wikiPageWikiLink
dbr:Valiant–Vazirani_theorem
Subject Item
dbr:Toda's_theorem
dbo:wikiPageWikiLink
dbr:Valiant–Vazirani_theorem
Subject Item
dbr:UP_(complexity)
dbo:wikiPageWikiLink
dbr:Valiant–Vazirani_theorem
Subject Item
dbr:Vijay_Vazirani
dbo:wikiPageWikiLink
dbr:Valiant–Vazirani_theorem
dbp:knownFor
dbr:Valiant–Vazirani_theorem
dbo:knownFor
dbr:Valiant–Vazirani_theorem
Subject Item
dbr:List_of_theorems
dbo:wikiPageWikiLink
dbr:Valiant–Vazirani_theorem
Subject Item
dbr:NP-completeness
dbo:wikiPageWikiLink
dbr:Valiant–Vazirani_theorem
Subject Item
dbr:Structural_complexity_theory
dbo:wikiPageWikiLink
dbr:Valiant–Vazirani_theorem
Subject Item
dbr:Valiant-Vazirani_Theorem
dbo:wikiPageWikiLink
dbr:Valiant–Vazirani_theorem
dbo:wikiPageRedirects
dbr:Valiant–Vazirani_theorem
Subject Item
dbr:Valiant-Vazirani_theorem
dbo:wikiPageWikiLink
dbr:Valiant–Vazirani_theorem
dbo:wikiPageRedirects
dbr:Valiant–Vazirani_theorem
Subject Item
wikipedia-en:Valiant–Vazirani_theorem
foaf:primaryTopic
dbr:Valiant–Vazirani_theorem