Program-size complexity of intial segments and domination reducibility
From MaRDI portal
Recommendations
- About Segment Complexity of Turing Reductions
- Characterization and lower bounds for branching program size using projective dimension
- Characterization and Lower Bounds for Branching Program Size Using Projective Dimension.
- Stochastic Algorithms: Foundations and Applications
- Strong and weak reducibility of algorithmic problems
- Polynomial time introreducibility
- Polynomial size \(\Omega\)-branching programs and their computational power
- scientific article; zbMATH DE number 3913677
- On the Algorithmic Complexity of Total Domination
- scientific article; zbMATH DE number 4051004
Cited in
(7)- Randomness and reducibility
- Unified characterizations of lowness properties via Kolmogorov complexity
- Lowness properties and randomness
- Randomness, computability, and density
- On the complexity of identifying head-elementary-set-free programs
- scientific article; zbMATH DE number 4076979 (Why is no real title available?)
- A characterization of c. e. random reals
This page was built for publication: Program-size complexity of intial segments and domination reducibility
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4941163)
