Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/ZPP_(complexity)> ?p ?o }
Showing triples 1 to 49 of
49
with 100 triples per page.
- ZPP_(complexity) abstract "In complexity theory, ZPP (zero-error probabilistic polynomial time) is the complexity class of problems for which a probabilistic Turing machine exists with these properties: It always returns the correct YES or NO answer. The running time is polynomial in expectation for every input.In other words, if the algorithm is allowed to flip a truly-random coin while it is running, it will always return the correct answer and, for a problem of size n, there is some polynomial p(n) such that the average running time will be less than p(n), even though it might occasionally be much longer. Such an algorithm is called a Las Vegas algorithm.Alternatively, ZPP can be defined as the class of problems for which a probabilistic Turing machine exists with these properties: It always runs in polynomial time. It returns an answer YES, NO or DO NOT KNOW. The answer is always either DO NOT KNOW or the correct answer. It returns DO NOT KNOW with probability at most 1/2 (and the correct answer otherwise).The two definitions are equivalent.The definition of ZPP is based on probabilistic Turing machines, but, for clarity, note that other complexity classes based on them include BPP and RP. The class BQP is based on another machine with randomness: the quantum computer.".
- ZPP_(complexity) wikiPageID "54772".
- ZPP_(complexity) wikiPageLength "8463".
- ZPP_(complexity) wikiPageOutDegree "21".
- ZPP_(complexity) wikiPageRevisionID "700236270".
- ZPP_(complexity) wikiPageWikiLink BPP_(complexity).
- ZPP_(complexity) wikiPageWikiLink BQP.
- ZPP_(complexity) wikiPageWikiLink Category:Probabilistic_complexity_classes.
- ZPP_(complexity) wikiPageWikiLink Complexity_class.
- ZPP_(complexity) wikiPageWikiLink Computational_complexity_theory.
- ZPP_(complexity) wikiPageWikiLink EXPTIME.
- ZPP_(complexity) wikiPageWikiLink Expected_value.
- ZPP_(complexity) wikiPageWikiLink Las_Vegas_algorithm.
- ZPP_(complexity) wikiPageWikiLink Low_(complexity).
- ZPP_(complexity) wikiPageWikiLink Markovs_inequality.
- ZPP_(complexity) wikiPageWikiLink P_(complexity).
- ZPP_(complexity) wikiPageWikiLink Probabilistic_Turing_machine.
- ZPP_(complexity) wikiPageWikiLink Quantum_computing.
- ZPP_(complexity) wikiPageWikiLink RP_(complexity).
- ZPP_(complexity) wikiPageWikiLink Time_complexity.
- ZPP_(complexity) wikiPageWikiLink Time_hierarchy_theorem.
- ZPP_(complexity) wikiPageWikiLink Turing_machine.
- ZPP_(complexity) wikiPageWikiLinkText "ZPP (complexity)".
- ZPP_(complexity) wikiPageWikiLinkText "ZPP".
- ZPP_(complexity) wikiPageWikiLinkText "expected polynomial runtime".
- ZPP_(complexity) wikiPageUsesTemplate Template:CZoo.
- ZPP_(complexity) wikiPageUsesTemplate Template:ComplexityClasses.
- ZPP_(complexity) wikiPageUsesTemplate Template:No_footnotes.
- ZPP_(complexity) subject Category:Probabilistic_complexity_classes.
- ZPP_(complexity) hypernym Class.
- ZPP_(complexity) type Class.
- ZPP_(complexity) comment "In complexity theory, ZPP (zero-error probabilistic polynomial time) is the complexity class of problems for which a probabilistic Turing machine exists with these properties: It always returns the correct YES or NO answer.".
- ZPP_(complexity) label "ZPP (complexity)".
- ZPP_(complexity) sameAs Q136355.
- ZPP_(complexity) sameAs ZPP_(تعقيد_حسابي).
- ZPP_(complexity) sameAs ZPP_(Komplexitätsklasse).
- ZPP_(complexity) sameAs ZPP_(complexité).
- ZPP_(complexity) sameAs ZPP.
- ZPP_(complexity) sameAs ZPP_(complessità).
- ZPP_(complexity) sameAs ZPP.
- ZPP_(complexity) sameAs ZPP.
- ZPP_(complexity) sameAs ZPP.
- ZPP_(complexity) sameAs m.0f8sh.
- ZPP_(complexity) sameAs Класс_ZPP.
- ZPP_(complexity) sameAs ZPP_(độ_phức_tạp).
- ZPP_(complexity) sameAs Q136355.
- ZPP_(complexity) sameAs ZPP_(複雜度).
- ZPP_(complexity) wasDerivedFrom ZPP_(complexity)?oldid=700236270.
- ZPP_(complexity) isPrimaryTopicOf ZPP_(complexity).