29 problems

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 $\mathbb{M}$ be the ambient nonstandard structure, let $\alpha$ be an oracle, and let $\Delta^b_1(\alpha)$-definable linear orders be the orders considered in the forcing const…

A polynomial-time linear order is a linear ordering definable by an oracle polynomial-time machine. The Factorization Hypothesis is the computational condition on such orders state…

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 $G$ be an undirected graph. The formula $\mathrm{SubsetConn}(G)$ expresses that every nonempty proper vertex subset has an edge to its complement, while $\mathrm{PathConn}(G)$…

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…

Let $U,V\subseteq\mathbb{N}$ be disjoint $\mathbf{NP}$-sets. A separator for $U$ and $V$ is a polynomial-time computable set $S\subseteq\mathbb{N}$ such that $U\subseteq S$ and…

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

Number-sort consequence conjecture. It is conjectured that $\mathsf{V}^1_2$ has more number-sort consequences than all the other theories mentioned so far.

NEXP circuit lower-bound consistency conjecture. The theory $\mathsf{V}^0_2$ is consistent with

Fisher inequality non-implication conjecture. There is no $p$ such that

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

Fisher inequality conjecture.

Oddtown converse conjecture.

Uniform counting principle conjecture.

Strong-system conjecture. The system $i_\infty EF$ is polynomially equivalent to the strong proof system of $S^1_2$.

Polynomial-length consistency conjecture. There are no such sequences of proofs whose lengths are polynomial in $n$.

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 $A$ and $B$ be two matrices, and let $\operatorname{DET}(A)$ denote the determinant function. Consider a formal theory that, loosely speaking, reasons with $\mathbf{NC^2}$ conc…

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, 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…