32 problems

The generalized probability coding conjecture for $P^G$
arXiv@arxiv
Let $B^{\sharp}$ be the domain of finite binary strings under consideration, and let $P^G(x)$ and $K^G(x)$ denote the corresponding generalized probability and complexity functions…
Conjectureopenalgorithmic-information-theory coding-theory
0
The enumerable probability coding conjecture for $P^E$
arXiv@arxiv
Let $B^{\sharp}$ be the domain of finite binary strings under consideration, and let $P^E(x)$ and $K^E(x)$ denote the corresponding enumerable measure and complexity functions. Wri…
Conjectureopenalgorithmic-information-theory coding-theory
0
The monotone complexity coding conjecture for $P^M$
arXiv@arxiv
Let $B^{\sharp}$ be the domain of finite binary strings under consideration, and let $P^M(x)$ and $K^M(x)$ denote the corresponding measure and complexity functions. Write…
Conjectureopenalgorithmic-information-theory coding-theory
0
The strengthened universal MDL convergence bound
arXiv@arxiv
Let $K$ be prefix Kolmogorov complexity, let $\boldsymbol{\vartheta}_0$ be the true parameter, and let $\Delta(k)$ denote the complexity difference used in the MDL setup. Strengthe…
Conjectureopenalgorithmic-information-theory convergence-rates minimum-description-length
0
Levin's conjecture equating monotone complexity with monotone a priori complexity
arXiv@arxiv
Let $U$ be the reference monotone machine. The monotone complexity of a finite binary string $x$ is … Let ${\bf M}(x)$ denote the corresponding monotone a priori probability. Levin…
Conjectureopenalgorithmic-information-theory kolmogorov-complexity
0
Equivalence of definitions of monotone conditional complexity
arXiv@arxiv
The paper considers several definitions of the complexity $K_*(y\mid x*)$ , including definitions based on minimal prediction error and an encoding-free characterization by non-nega…
Conjectureopenalgorithmic-information-theory kolmogorov-complexity
2
Conjecture on machine representation of conditional complexity bounds
arXiv@arxiv
Let $E$ be a set defining conditional complexity by $C_E(x|y)=\min\{\ell(p)\mid\langle p,y,x\rangle\in E\}$ . Let $C_T(x|y)$ denote the conditional complexity induced by a twice pre…
Conjectureopenalgorithmic-information-theory computability conditional-complexity
0
Non-approximability conjecture for the universal distributions $D$ and $\hat D$
arXiv@arxiv
Non-approximability conjecture. $D$ and $\hat D$ are not even approximable (limit-computable), but lie somewhere higher in the arithmetic hierarchy.
Conjectureopenalgorithmic-information-theory computability-theory semimeasures
1
Universal convergence bound for MDL predictions of Bernoulli sequences
arXiv@arxiv
Let $\theta_0$ be the true Bernoulli parameter, let $\theta^x$ denote the MDL prediction based on the observed sequence, let $K(\theta_0)$ be the prefix Kolmogorov complexity of…
Conjectureopenalgorithmic-information-theory mdl prediction
0
The reprogrammability conjecture for BDM 2.0
arXiv@arxiv
Let $x_i$ be objects with admissible program sets $\mathcal{P}(x_i)$ , let $u\in\mathcal{P}(x_i)$ satisfy $U(u)=x_i$ , and let $\hat K$ denote the estimated description-length comple…
Conjectureopenalgorithmic-complexity algorithmic-information-theory descriptional-complexity
0
The smaller-partition conjecture for algorithmic graph analysis
arXiv@arxiv
Smaller-partition conjecture. Since the analyzed graphs are small, partitioning their adjacency matrices into smaller sub-matrices should be more favorable.
Conjectureopenalgorithmic-information-theory graph-algorithms graph-structure
0
The landscape criterion for good universal fixed-length codebooks
arXiv@arxiv
Landscape criterion. We conjecture that, for any additively optimal UTM, a good UFCC $U$ should have a landscape—that is, an ordering of codebooks—similar to the UTM's landscape in…
Conjectureopenalgorithmic-information-theory causal-inference universal-coding
0
The conjecture that simpler computational models converge faster
arXiv@arxiv
Simplicity–convergence conjecture. Simpler models converge faster than more complex or artificial ones.
Conjectureopenalgorithmic-information-theory computational-models kolmogorov-complexity
0
The AIT covering-number conjecture for optimal data-point selection
arXiv@arxiv
The optimal number of data points refers to the number of data points selected from an algorithmic information theory (AIT) perspective, and covering numbers are the quantities use…
Conjectureopenalgorithmic-information-theory covering-numbers kernel-learning
0
Conjecture on total conditional complexity for the remaining object pairs
arXiv@arxiv
Remaining-pairs conjecture. For every remaining pair of objects $X,Y$ , the answer to the second question is negative.
Conjectureopenalgorithmic-information-theory kolmogorov-complexity
0
Conjecture on total conditional complexity for small objects
arXiv@arxiv
Small-object conjecture. For every small object $X$ , the answer to the first question is negative: there do not exist constants $c,d$ such that
Conjectureopenalgorithmic-information-theory kolmogorov-complexity
0
The conjecture that separate discussion of the convergence and approximation replies explains the overlooked tension
arXiv@arxiv
The paper discusses Solomonoff prediction, including Putnam's diagonal argument and the relationship between the convergence reply and the approximation reply. Conjecture. The rela…
Conjectureopenalgorithmic-information-theory solomonoff-prediction
1
The search-to-profile reduction conjecture
arXiv@arxiv
Search-to-profile reduction. Given this information, one can find, via a polynomial probabilistic algorithm, strings $y_1',\ldots,y_m'$ such that the tuple…
Conjectureopenalgorithmic-information-theory kolmogorov-complexity search-reductions
1
The existence conjecture for data-compressing effective ad hoc descriptions
arXiv@arxiv
A number is compressed by a non-constructive unique effective description when the validity of the description can be checked effectively given the number, but the number cannot be…
Conjectureopenalgorithmic-information-theory computability-theory
1
Lutz's dimension spectrum conjecture for planar lines
arXiv@arxiv
Lutz's dimension spectrum conjecture. For every line $L_{a,b}$ , the spectrum $\operatorname{sp}(L_{a,b})$ contains a unit interval. The conjecture concerns which effective dimensio…
Conjectureopenalgorithmic-information-theory dimension-spectrum effective-dimension
1
Schmidhuber's continuum quantum-field-theory conjecture for the critical ensemble
arXiv@arxiv
Consider the ensemble of bit string histories generated by a universal Turing machine at the critical point, where the partition function reaches Chaitin's halting probability…
Conjectureopenalgorithmic-information-theory quantum-field-theory string-theory
0
Schmidhuber's string-theoretic formulation conjecture for the critical bit-string ensemble
arXiv@arxiv
Let a universal Turing machine define an ensemble of bit string histories, with the critical temperature corresponding to the Chaitin point at which the partition function reaches…
Conjectureopenalgorithmic-information-theory quantum-field-theory string-theory
0
Levin's conjecture that computable and Martin-Löf random sequences exhaust invariant properties
arXiv@arxiv
Consider the algebra of invariant properties obtained by identifying invariant sets whose symmetric difference is negligible. Let $\mathbf{c}$ be the class generated by computable…
Conjecturerefutedalgorithmic-information-theory computability-theory kolmogorov-complexity
0
Conjecture on the impossibility of universally ultra-tight oracle-use bounds
arXiv@arxiv
Let $X$ and $Y$ be infinite binary sequences, and let an oracle computation of $X$ by $Y$ have an oracle-use function measuring how many bits of $Y$ are queried to compute the firs…
Conjectureopenalgorithmic-information-theory computability-theory kolmogorov-complexity
2
Entropy representation by prefix Kolmogorov complexity
arXiv@arxiv
Entropy-complexity conjecture. For $H=\overline{H}$ or $H=\underline{H}$ , one has
Conjectureopenalgorithmic-information-theory quantum-information
0