Computational depth and reducibility
From MaRDI portal
Recommendations
- Computational depth and reducibility
- Recursive computational depth
- Computational irreducibility and computational analogy
- Natural complexity, computational complexity and depth
- First-order reduction and computational complexity
- Computational depth: Concept and applications
- Reductions, completeness and the hardness of approximability
- Computing depth orders and related problems
- scientific article; zbMATH DE number 1042857
Cites work
- A formal theory of inductive inference. Part II
- A Theory of Program Size Formally Identical to Information Theory
- Algebra of invariant properties of binary sequences
- Algorithms and Randomness
- Almost everywhere high nonuniform complexity
- An observation on probability versus randomness with applications to complexity classes
- Classes of Recursively Enumerable Sets and Degrees of Unsolvability
- Complexity oscillations in infinite binary sequences
- Computational Complexity of Probabilistic Turing Machines
- Descriptive set theory
- Every sequence is reducible to a random one
- Families of recursive predicates of measure zero
- scientific article; zbMATH DE number 3427210 (Why is no real title available?)
- scientific article; zbMATH DE number 3112450 (Why is no real title available?)
- scientific article; zbMATH DE number 4060392 (Why is no real title available?)
- scientific article; zbMATH DE number 4072382 (Why is no real title available?)
- scientific article; zbMATH DE number 4088925 (Why is no real title available?)
- scientific article; zbMATH DE number 4091484 (Why is no real title available?)
- scientific article; zbMATH DE number 4093436 (Why is no real title available?)
- scientific article; zbMATH DE number 46153 (Why is no real title available?)
- scientific article; zbMATH DE number 107482 (Why is no real title available?)
- scientific article; zbMATH DE number 107774 (Why is no real title available?)
- scientific article; zbMATH DE number 192916 (Why is no real title available?)
- scientific article; zbMATH DE number 3489016 (Why is no real title available?)
- scientific article; zbMATH DE number 3492569 (Why is no real title available?)
- scientific article; zbMATH DE number 3532844 (Why is no real title available?)
- scientific article; zbMATH DE number 3541937 (Why is no real title available?)
- scientific article; zbMATH DE number 3559552 (Why is no real title available?)
- scientific article; zbMATH DE number 3557755 (Why is no real title available?)
- scientific article; zbMATH DE number 3637728 (Why is no real title available?)
- scientific article; zbMATH DE number 1142293 (Why is no real title available?)
- scientific article; zbMATH DE number 4119313 (Why is no real title available?)
- scientific article; zbMATH DE number 3446413 (Why is no real title available?)
- scientific article; zbMATH DE number 3291134 (Why is no real title available?)
- scientific article; zbMATH DE number 3307567 (Why is no real title available?)
- scientific article; zbMATH DE number 3311755 (Why is no real title available?)
- scientific article; zbMATH DE number 3344793 (Why is no real title available?)
- scientific article; zbMATH DE number 3190627 (Why is no real title available?)
- Incompleteness theorems for random reals
- Learning Simple Concepts under Simple Distributions
- Logical basis for information theory and probability theory
- On Languages Reducible to Algorithmically Random Languages
- On Suborderings of Degrees of Recursive Unsolvability
- On the Length of Programs for Computing Finite Binary Sequences
- On the Length of Programs for Computing Finite Binary Sequences
- Process complexity and effective random tests
- Randomness conservation inequalities; information and independence in mathematical theories
- THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
- The definition of random sequences
Cited in
(28)- Lowness and logical depth
- Limit-depth and DNR degrees
- Weakly useful sequences
- Recursive computational depth.
- Time-bounded Kolmogorov complexity and Solovay functions
- Feasible reductions to Kolmogorov-Loveland stochastic sequences
- Quantum logical depth and shallowness of streaming data by one-way quantum finite-state transducers (preliminary report)
- Searching for shortest and least programs
- Computational depth: Concept and applications
- Relativized depth
- Phase transition between unidirectionality and bidirectionality
- Depth, highness and DNR degrees
- On the Polynomial Depth of Various Sets of Random Strings
- Time-Bounded Kolmogorov Complexity and Solovay Functions
- On the difference between finite-state and pushdown depth
- Constant Depth Reducibility
- Computing and Verifying Depth Orders
- Depth, highness and DNR degrees
- Recursive computational depth
- Computational depth and reducibility
- Weakly useful sequences
- Sophistication vs logical depth
- The limits of depth reduction for arithmetic formulas
- Deep _1⁰ classes
- STACS 2005
- Recursively enumerable reals and Chaitin \(\Omega\) numbers
- Bridging computational notions of depth
- Depth as randomness deficiency
This page was built for publication: Computational depth and reducibility
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1334655)
