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

A generator is a map $g:{0,1}^*\rightarrow{0,1}^*$ whose restriction to inputs of length $n$ maps into strings of length $m(n)>n$ and is computed by circuits of size polynomial in…

Let a lattice be a discrete subgroup of Euclidean space, and let its shortest nonzero integer vector length be the relevant lattice parameter. Lattice shortest-vector hardness conj…

Let Feige's Hypothesis be the assertion that no efficient algorithm can prove the unsatisfiability of a random $3$-SAT formula with high probability, even when the formula has a sm…

Let $R$ be the set of Kolmogorov-random binary strings defined using the fixed universal Turing machine $U$, and let $k$ be the threshold supplied by Chaitin's incompleteness theor…

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…

Analyzability requires lower bounds or proofs that are hard to find. For every propositional proof system $Q$, if $Q$ is analyzable, then $Q$ is not p-optimal.

Analyzability requires lower bounds. For every propositional proof system $Q$, if $Q$ is analyzable, then $Q$ is not optimal.

Near-threshold resolution lower-bound conjecture. For an instance size $n$ with no solution, $n\notin S$, if

Let $\mathcal{S}$ and $\mathcal{T}$ be consistent theories, with $\mathcal{T}$ strictly stronger than $\mathcal{S}$, and let $\mathfrak{I}$ be a collection of sentences unprovable…

Let $R$ be the set of Kolmogorov-random strings, and let $t$ be a proof-length bound for statements asserting that no proof of $x\in R$ has length at most $t$. Exhaustive-search co…

Let $g$ be a polynomial-time function that maps inputs of length $n$ to outputs of length $n+1$, and let $rng(g)$ denote its range. Proof search conjecture. There exists such a fun…

Let $Q$ be a propositional proof system. A theory $\mathcal{T}$ is a conservative extension of a base theory when it extends that theory without proving any new sentences in the ba…

Let $\mathcal{T}$ be the theory used to define $H'$, and let $H'$ be the collection of dense sets of true $\mathcal{T}$-unprovable sentences described in the source. Given a nondet…

Let $H'$ be the set comprising $H$ and other dense sets of true sentences unprovable in $\mathcal{T}$, including the specified sets associated with universal Turing machines and Tu…

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…

The class UP consists of languages accepted by polynomial-time nondeterministic Turing machines having a unique accepting computation on every accepted input. No complete UP set co…

A p-optimal proof system is a propositional proof system that polynomially simulates every propositional proof system. No p-optimal proof system conjecture. There exists no p-optim…

A disjoint NP pair is a pair $(A,B)$ of disjoint languages in NP, and polynomial reduction between pairs maps the first component to the first and the second to the second. No comp…

Let $\mathcal T$ be the class of theories under consideration. For a consistent universal sentence $\Phi$, let $HCS(\Phi)$ be its Herbrand Consistency Search problem: given finitel…

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…