An observation on probability versus randomness with applications to complexity classes
From MaRDI portal
Recommendations
Cites work
- Complexity oscillations in infinite binary sequences
- 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 3291134 (Why is no real title available?)
- Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
- Polynomial-time reducibilities and ``almost all oracle sets
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- The definition of random sequences
- The polynomial-time hierarchy and sparse oracles
- Turing machines that take advice
- With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
Cited in
(22)- Dimension extractors and optimal decompression
- On the relation between descriptional complexity and algorithmic probability
- An improved zero-one law for algorithmically random sequences
- Probabilistic type-2 operators and ``almost-classes
- Computational depth and reducibility
- On collapsing the polynomial-time hierarchy
- Structural properties of bounded relations with an application to NP optimization problems
- Feasible reductions to Kolmogorov-Loveland stochastic sequences
- Dimension characterizations of complexity classes
- A variation on the zero-one law
- Limits on the Computational Power of Random Strings
- scientific article; zbMATH DE number 4131664 (Why is no real title available?)
- A relation between correctness and randomness in the computation of probabilistic algorithms
- scientific article; zbMATH DE number 4049050 (Why is no real title available?)
- Exact Pairs for Abstract Bounded Reducibilities
- Some notes on Rissanen's stochastic complexity
- Computational depth and reducibility
- On the robustness of ALMOST-$\mathcal {R}$
- scientific article; zbMATH DE number 3995648 (Why is no real title available?)
- On complexity classes and algorithmically random languages (extended abstract)
- Complexity classes of equivalence problems revisited
- Random permutations in computational complexity
This page was built for publication: An observation on probability versus randomness with applications to complexity classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4298369)
