14 problems

Fix a base theory $\mathcal S$ and let $R$ be the set of Kolmogorov-random strings defined using the fixed universal machine and additive constant. Let $N_R^{\mathcal S}$ be the ma…

Fix a universal Turing machine $U$, a constant $c_U$, and let $R$ be the set of strings $x$ satisfying $K_U(x)\geq |x|-c_U$, where $K_U(x)$ is the plain Kolmogorov complexity of…

Let $\mathcal S$ be the base arithmetic theory under consideration, and let $Con_{\mathcal S}(n)$ denote its bounded consistency statement at length $n$. Write…

Let $\mathcal{S}$ be a theory, let $\phi$ be a sentence, and let $n$ be a natural number. Write $Con_{\mathcal{S}+\phi}(n)$ for the bounded consistency statement for…

Let $\mathsf{MSO}^\phi(\sharp)$ be monadic second-order logic with the Härtig quantifier, and call an arithmetical predicate directly definable when it is defined by the logic in t…

Bounded-arithmetic conjecture for Arrow's theorem. The first-order formalisation of Arrow's theorem is provable in

Constant-depth Frege oddtown conjecture. For each $d\in\mathbb{N}$ and each prime $p\neq 2$,

Polynomial consistency-speedup conjecture. For every sound $\Delta^b_1(S^1_2)$ theory $S$ and every $l\in\omega$, there exists a sound $\Delta^b_1(S^1_2)$ theory $T$ such that

Let $f$ be a polynomial-time algorithm, viewed as a function symbol of $\mathsf{PV}$, and let … where $\psi_{\mathsf{SAT}}(x,y)$ expresses that $y$ satisfies the Boolean formula en…

Let $T\in\mathcal T$ be a theory axiomatized by a universal sentence, and let $HCS(T)$ denote its Herbrand Consistency Search problem. Universal-theory Herbrand consistency conject…

Let $\mathcal T$ be the class of theories under consideration. A TFNP problem is a total polynomial search problem, and $\operatorname{TFNP}(T)$ is the class of such problems prova…

Let $\mathcal T$ be the class of theories under consideration, and let $\Sigma^b_1RFN_T(\bar n)$ denote the finite $\Sigma^b_1$ reflection principle for $T$. Nonuniform reflection…

Let $\mathcal T$ be the class of theories under consideration, and let $Con_S$ mean that $S$ is consistent. Consistency-provability strengthening conjecture. For every…

Let ${\rm IDelta}_0$ be the bounded-induction theory of arithmetic, let ${\rm \Omega}_n$ denote the corresponding family of axioms, and let ${\rm HCon}^*({\rm IDelta}_0)$ denote the…