An observation on probability versus randomness with applications to complexity classes

DOI10.1007/BF01578842zbMath0819.68056MaRDI QIDQ4298369

Jack H. Lutz, Ronald V. Book, Klaus W. Wagner

Publication date: 27 August 1995

Published in: Mathematical Systems Theory (Search for Journal in Brave)

zbMATH Keywords

complexity classes

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (10)

Computational depth and reducibility ⋮ Computational depth and reducibility ⋮ On collapsing the polynomial-time hierarchy ⋮ Exact Pairs for Abstract Bounded Reducibilities ⋮ An improved zero-one law for algorithmically random sequences ⋮ Feasible reductions to Kolmogorov-Loveland stochastic sequences ⋮ Limits on the Computational Power of Random Strings ⋮ Dimension extractors and optimal decompression ⋮ On the robustness of ALMOST-$\mathcal {R}$ ⋮ Structural properties of bounded relations with an application to NP optimization problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Turing machines that take advice
• With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
• Polynomial-time reducibilities and ``almost all oracle sets
• The polynomial-time hierarchy and sparse oracles
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
• Complexity oscillations in infinite binary sequences
• The definition of random sequences

This page was built for publication: An observation on probability versus randomness with applications to complexity classes