We study the parameterized complexity of the problem to decide whether a given natural number n satisfies a given $\Delta _0$-formula $\varphi (x)$; the parameter is the size of $\varphi $. This parameterization focusses attention on instances where n is large compared to the size of $\varphi $. We show unconditionally that this problem does not belong to the parameterized analogue of $\mathsf {AC}^0$. From this we derive that certain natural upper bounds on the complexity of our parameterized problem imply certain separations of classical complexity classes. This connection is obtained via an analysis of a parameterized halting problem. Some of these upper bounds follow assuming that $I\Delta _0$ proves the MRDP theorem in a certain weak sense.

Cook and Reckhow [5] pointed out that $\mathcal {N}\mathcal {P} \neq co\mathcal {N}\mathcal {P}$ iff there is no propositional proof system that admits polynomial size proofs of all tautologies. The theory of proof complexity generators aims at constructing sets of tautologies hard for strong and possibly for all proof systems. We focus on a conjecture from [16] in foundations of the theory that there is a proof complexity generator hard for all proof systems. This can be equivalently formulated (for p-time generators) without a reference to proof complexity notions as follows:

• • There exists a p-time function g stretching each input by one bit such that its range $rng(g)$ intersects all infinite $\mathcal {N}\mathcal {P}$ sets.

$\bigvee $

$\bigvee $

$\mathcal {N}\mathcal {P}$

$\mathcal {N}\mathcal {P}$

Given a sound first-order p-time theory T capable of formalizing syntax of first-order logic we define a p-time function $g_T$ that stretches all inputs by one bit and we use its properties to show that T must be incomplete. We leave it as an open problem whether for some T the range of $g_T$ intersects all infinite ${\mbox {NP}}$ sets (i.e., whether it is a proof complexity generator hard for all proof systems).

A propositional version of the construction shows that at least one of the following three statements is true:

1. 1. There is no p-optimal propositional proof system (this is equivalent to the non-existence of a time-optimal propositional proof search algorithm).

2. 2. $E \not \subseteq P/poly$.

3. 3. There exists function h that stretches all inputs by one bit, is computable in sub-exponential time, and its range $Rng(h)$ intersects all infinite ${\text {NP}}$ sets.

An oracle A is low-for-speed if it is unable to speed up the computation of a set which is already computable: if a decidable language can be decided in time $t(n)$ using A as an oracle, then it can be decided without an oracle in time $p(t(n))$ for some polynomial p. The existence of a set which is low-for-speed was first shown by Bayer and Slaman who constructed a non-computable computably enumerable set which is low-for-speed. In this paper we answer a question previously raised by Bienvenu and Downey, who asked whether there is a minimal degree which is low-for-speed. The standard method of constructing a set of minimal degree via forcing is incompatible with making the set low-for-speed; but we are able to use an interesting new combination of forcing and full approximation to construct a set which is both of minimal degree and low-for-speed.

In [20] Krajíček and Pudlák discovered connections between problems in computational complexity and the lengths of first-order proofs of finite consistency statements. Later Pudlák [25] studied more statements that connect provability with computational complexity and conjectured that they are true. All these conjectures are at least as strong as $\mathsf {P}\neq \mathsf {NP}$ [23–25].One of the problems concerning these conjectures is to find out how tightly they are connected with statements about computational complexity classes. Results of this kind had been proved in [20, 22].In this paper, we generalize and strengthen these results. Another question that we address concerns the dependence between these conjectures. We construct two oracles that enable us to answer questions about relativized separations asked in [19, 25] (i.e., for the pairs of conjectures mentioned in the questions, we construct oracles such that one conjecture from the pair is true in the relativized world and the other is false and vice versa). We also show several new connections between the studied conjectures. In particular, we show that the relation between the finite reflection principle and proof systems for existentially quantified Boolean formulas is similar to the one for finite consistency statements and proof systems for non-quantified propositional tautologies.

We introduce a notion of complexity of diagrams (and, in particular, of objects and morphisms) in an arbitrary category, as well as a notion of complexity of functors between categories equipped with complexity functions. We discuss several examples of this new definition in categories of wide common interest such as finite sets, Boolean functions, topological spaces, vector spaces, semilinear and semialgebraic sets, graded algebras, affine and projective varieties and schemes, and modules over polynomial rings. We show that on one hand categorical complexity recovers in several settings classical notions of nonuniform computational complexity (such as circuit complexity), while on the other hand it has features that make it mathematically more natural. We also postulate that studying functor complexity is the categorical analog of classical questions in complexity theory about separating different complexity classes.

We prove that the Wadge order on the Borel subsets of the Scott domain is not a well-quasi-order, and that this feature even occurs among the sets of Borel rank at most 2. For this purpose, a specific class of countable 2-colored posets $\mathbb{P}_{emb} $ equipped with the order induced by homomorphisms is embedded into the Wadge order on the $\Delta _2^0 $-degrees of the Scott domain. We then show that $\mathbb{P}_{emb} $ admits both infinite strictly decreasing chains and infinite antichains with respect to this notion of comparison, which therefore transfers to the Wadge order on the $\Delta _2^0 $-degrees of the Scott domain.

Motivated by the problem of finding finite versions of classical incompleteness theorems, we present some conjectures that go beyond NP ≠ coNP. These conjectures formally connect computational complexity with the difficulty of proving some sentences, which means that high computational complexity of a problem associated with a sentence implies that the sentence is not provable in a weak theory, or requires a long proof. Another reason for putting forward these conjectures is that some results in proof complexity seem to be special cases of such general statements and we want to formalize and fully understand these statements. Roughly speaking, we are trying to connect syntactic complexity, by which we mean the complexity of sentences and strengths of the theories in which they are provable, with the semantic concept of complexity of the computational problems represented by these sentences.

We have introduced the most fundamental conjectures in our earlier works [27, 33–35]. Our aim in this article is to present them in a more systematic way, along with several new conjectures, and prove new connections between them and some other statements studied before.