Helping by unambiguous computation and probabilistic computation

DOI10.1007/BF02679447MaRDI QIDQ675865zbMATH OpenFDO

Authors Patrizio Cintioli, Riccardo Silvestri

Publication date 18 November 1997

Published in Theory of Computing Systems (Search for Journal in Brave)

zbMATH Keywords

probabilistic computationoracles

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• On helping by robust oracle machines
• The Helping Hierarchy
• On helping by parity-like languages
• Revisiting a result of Ko

Cites work

• scientific article; zbMATH DE number 46423 (Why is no real title available?)
• scientific article; zbMATH DE number 192916 (Why is no real title available?)
• scientific article; zbMATH DE number 578252 (Why is no real title available?)
• scientific article; zbMATH DE number 1414287 (Why is no real title available?)
• scientific article; zbMATH DE number 1414307 (Why is no real title available?)
• A uniform approach to define complexity classes
• CREW PRAM<scp>s</scp> and Decision Trees
• Complexity classes and sparse oracles
• ON THE LIMITATIONS OF LOCALLY ROBUST POSITIVE REDUCTIONS
• On helping by robust oracle machines
• On the power of parity polynomial time
• Query complexity, or why is it difficult to separate NP^ A coNP^ A from P^ A by random oracles A?
• RELATIVIZABLE AND NONRELATIVIZABLE THEOREMS IN THE POLYNOMIAL THEORY OF ALGORITHMS
• Relativized Questions Involving Probabilistic Algorithms
• Robust algorithms: a different approach to oracles
• Robust machines accept easy sets
• Self-reducibility
• Structural properties for feasibly computable classes of type two

Cited in

(4)

• scientific article; zbMATH DE number 3483592 (Why is no real title available?)
• Revisiting a result of Ko
• The Helping Hierarchy
• On helping by parity-like languages

This page was built for publication: Helping by unambiguous computation and probabilistic computation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q675865)