Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/Valiant–Vazirani_theorem> ?p ?o }
Showing triples 1 to 35 of
35
with 100 triples per page.
- Valiant–Vazirani_theorem abstract "The Valiant–Vazirani theorem is a theorem in computational complexity theory. 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 theorem states that if there is a polynomial time algorithm for Unambiguous-SAT, then NP=RP.The proof is based on the Mulmuley–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.".
- Valiant–Vazirani_theorem wikiPageID "3003434".
- Valiant–Vazirani_theorem wikiPageLength "4104".
- Valiant–Vazirani_theorem wikiPageOutDegree "19".
- Valiant–Vazirani_theorem wikiPageRevisionID "678371613".
- Valiant–Vazirani_theorem wikiPageWikiLink Boolean_satisfiability_problem.
- Valiant–Vazirani_theorem wikiPageWikiLink Category:Structural_complexity_theory.
- Valiant–Vazirani_theorem wikiPageWikiLink Category:Theorems_in_computational_complexity_theory.
- Valiant–Vazirani_theorem wikiPageWikiLink Computational_complexity_theory.
- Valiant–Vazirani_theorem wikiPageWikiLink Isolation_lemma.
- Valiant–Vazirani_theorem wikiPageWikiLink Leslie_Valiant.
- Valiant–Vazirani_theorem wikiPageWikiLink NP-completeness.
- Valiant–Vazirani_theorem wikiPageWikiLink NP_(complexity).
- Valiant–Vazirani_theorem wikiPageWikiLink Non-deterministic_Turing_machine.
- Valiant–Vazirani_theorem wikiPageWikiLink P_(complexity).
- Valiant–Vazirani_theorem wikiPageWikiLink Promise_problem.
- Valiant–Vazirani_theorem wikiPageWikiLink RP_(complexity).
- Valiant–Vazirani_theorem wikiPageWikiLink Random_self-reducibility.
- Valiant–Vazirani_theorem wikiPageWikiLink Theoretical_computer_science.
- Valiant–Vazirani_theorem wikiPageWikiLink UP_(complexity).
- Valiant–Vazirani_theorem wikiPageWikiLink Vijay_Vazirani.
- Valiant–Vazirani_theorem wikiPageWikiLinkText "Valiant–Vazirani theorem".
- Valiant–Vazirani_theorem wikiPageUsesTemplate Template:Reflist.
- Valiant–Vazirani_theorem subject Category:Structural_complexity_theory.
- Valiant–Vazirani_theorem subject Category:Theorems_in_computational_complexity_theory.
- Valiant–Vazirani_theorem hypernym Theorem.
- Valiant–Vazirani_theorem type Redirect.
- Valiant–Vazirani_theorem type Theorem.
- Valiant–Vazirani_theorem comment "The Valiant–Vazirani theorem is a theorem in computational complexity theory.".
- Valiant–Vazirani_theorem label "Valiant–Vazirani theorem".
- Valiant–Vazirani_theorem sameAs Q7911648.
- Valiant–Vazirani_theorem sameAs m.08jyrl.
- Valiant–Vazirani_theorem sameAs Q7911648.
- Valiant–Vazirani_theorem wasDerivedFrom Valiant–Vazirani_theorem?oldid=678371613.
- Valiant–Vazirani_theorem isPrimaryTopicOf Valiant–Vazirani_theorem.