70 problems

By a generator $g$ we mean a map whose restriction $g_n$ to $\{0,1\}^n$ has range contained in $\{0,1\}^m$, where $m=m(n)>n$, and is computed by a circuit of size $m^{O(1)}$. For…

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

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…

Finite-tower proof-length conjecture. There is a finite tower of exponentiations that gives an upper bound on the lengths of proofs of true sentences in $\mathsf{RCF}$.

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…

FP-completeness conjecture for the search version of $\PAP_\Res$. The improvement of the paper's NP-hardness result to weaker systems is impossible, and the search problem of…

Quasi-polynomial PHP formalization conjecture. The PHP lower bound might be formalizable in these systems, at least in quasi-polynomial size.

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.

Let $L$ and $R$ be languages in $\mathbf{NP}$ with $L\cap R=\emptyset$. A separator for the disjoint $\mathbf{NP}$ pair $(L,R)$ is a language $S$ such that $L\subseteq S$ and…

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

Overarching resolution conjecture. Some condition of the form in Theorem 3 asserts the resolution of most open questions in complexity theory.

A hitting formula is a set of Boolean clauses such that no two clauses can be simultaneously falsified. A hitting formula is unsatisfiable when no Boolean assignment satisfies all…

Consider theories such as ZFC and an isomorphism between sentences that are impossible to prove and families of sentences that are hard to prove efficiently. True-unprovable-senten…

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 $R^*$ be the class of strings defined using an oracle $O$ for the program $p$ and a compression threshold $|p|\leq f(|x|)$, for any decreasing function $f$. Let $\mathcal{S}$ a…

Let $R$ be the set of Kolmogorov-random binary strings, where $x\in R$ means that no program of length at most $|x|/2$ outputs $x$. Let $\mathcal{S}$ and $\mathcal{T}$ be consisten…

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…