Helping by unambiguous computation and probabilistic computation

DOI10.1007/BF02679447zbMath0876.68065MaRDI QIDQ675865

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)

Related Items (2)

Revisiting a result of Ko ⋮ The Helping Hierarchy

Cites Work

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

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