Matches in DBpedia 2016-04 for { <http://wikidata.dbpedia.org/resource/Q7911648> ?p ?o }
Showing triples 1 to 21 of
21
with 100 triples per page.
- Q7911648 subject Q13540920.
- Q7911648 subject Q8851973.
- Q7911648 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.".
- Q7911648 wikiPageWikiLink Q1190223.
- Q7911648 wikiPageWikiLink Q1190846.
- Q7911648 wikiPageWikiLink Q130203.
- Q7911648 wikiPageWikiLink Q13540920.
- Q7911648 wikiPageWikiLink Q205084.
- Q7911648 wikiPageWikiLink Q215206.
- Q7911648 wikiPageWikiLink Q2878974.
- Q7911648 wikiPageWikiLink Q6085965.
- Q7911648 wikiPageWikiLink Q628036.
- Q7911648 wikiPageWikiLink Q7291990.
- Q7911648 wikiPageWikiLink Q846354.
- Q7911648 wikiPageWikiLink Q875276.
- Q7911648 wikiPageWikiLink Q8851973.
- Q7911648 wikiPageWikiLink Q906584.
- Q7911648 wikiPageWikiLink Q92702.
- Q7911648 wikiPageWikiLink Q93154.
- Q7911648 comment "The Valiant–Vazirani theorem is a theorem in computational complexity theory.".
- Q7911648 label "Valiant–Vazirani theorem".