Helping by unambiguous computation and probabilistic computation

DOI10.1007/BF02679447zbMATH Open0876.68065MaRDI QIDQ675865FDOQ675865

Authors: Patrizio Cintioli, Riccardo Silvestri 

Publication date: 18 November 1997

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

Recommendations

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

zbMATH Keywords

probabilistic computationoracles

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• A uniform approach to define complexity classes
• Title not available (Why is that?)
• Robust algorithms: a different approach to oracles
• On helping by robust oracle machines
• Complexity classes and sparse oracles
• Self-reducibility
• Title not available (Why is that?)
• Title not available (Why is that?)
• RELATIVIZABLE AND NONRELATIVIZABLE THEOREMS IN THE POLYNOMIAL THEORY OF ALGORITHMS
• CREW PRAM<scp>s</scp> and Decision Trees
• Relativized Questions Involving Probabilistic Algorithms
• ON THE LIMITATIONS OF LOCALLY ROBUST POSITIVE REDUCTIONS
• Structural properties for feasibly computable classes of type two
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the power of parity polynomial time
• 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

Cited In (4)

• Title not available (Why is that?)
• 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)