On relativized probabilistic polynomial time algorithms

DOI10.2969/JMSJ/04910015MaRDI QIDQ1389852zbMATH OpenOpenAlexFDO

Authors Hisao Tanaka, Masafumi Kudoh

Publication date 10 November 1998

Published in Journal of the Mathematical Society of Japan (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2969/jmsj/04910015

zbMATH Keywords

polynomial time algorithmsrecursive oracle

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10)

Recommendations

• scientific article; zbMATH DE number 3995648
• scientific article; zbMATH DE number 4049050
• On relativized exponential and probabilistic complexity classes
• Restricted relativizations of probabilistic polynomial time

Cited in

(10)

• RELATIVIZABLE AND NONRELATIVIZABLE THEOREMS IN THE POLYNOMIAL THEORY OF ALGORITHMS
• Complexity of the \(r\)-query tautologies in the presence of a generic oracle
• scientific article; zbMATH DE number 2011858 (Why is no real title available?)
• Alternative proof for the localization of Sinai's walk
• Relativized questions involving probabilistic algorithms
• scientific article; zbMATH DE number 3995648 (Why is no real title available?)
• Restricted relativizations of probabilistic polynomial time
• Hausdorff dimension and oracle constructions
• Probabilistic parameterized polynomial time
• An observation on probability versus randomness with applications to complexity classes

This page was built for publication: On relativized probabilistic polynomial time algorithms

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