A promise problem \(\Pi = (\Pi _{\mathrm{yes}}, \Pi _{\mathrm{no}})\) is a pair of disjoint languages; inputs outside \(\Pi _{\mathrm{yes}} \cup \Pi _{\mathrm{no}}\) are unconstrained. For a language class \(\mathcal{C}\), \(\Pi \) lies in the lifted class \(\mathrm{Promise}\, \mathcal{C}\) when some completion \(L \in \mathcal{C}\) satisfies \(\Pi _{\mathrm{yes}} \subseteq L\) and \(L \cap \Pi _{\mathrm{no}} = \emptyset \). \(\mathsf{PromiseP}\) and \(\mathsf{PromiseNP}\) (and \(\mathsf{PromiseCoNP}\)) are the lifts of \(\mathsf{P}\) and \(\mathsf{NP}\) (and \(\mathsf{coNP}\)). An ordinary language \(L\) embeds as the total promise problem \((L, \overline{L})\).

A map \(f\) is side-preserving from \(\Pi \) to \(\Pi '\) when it sends \(\Pi _{\mathrm{yes}}\) into \(\Pi '_{\mathrm{yes}}\) and \(\Pi _{\mathrm{no}}\) into \(\Pi '_{\mathrm{no}}\); a polynomial-time promise reduction is a side-preserving map \(f \in \mathsf{FP}\). For a language class \(\mathcal{C}\), a promise problem is \(\mathcal{C}\)-hard when the total embedding of every language of \(\mathcal{C}\) reduces to it in this sense, and \(\mathcal{C}\)-complete when in addition it lies in \(\mathrm{Promise}\, \mathcal{C}\). Promise-\(\mathsf{NP}\)-hardness and promise-\(\mathsf{NP}\)-completeness are the case \(\mathcal{C} = \mathsf{NP}\).

\(\mathsf{PromiseSIZE}(s)\) and \(\mathsf{PromisePPoly}\) are the completion lifts of \(\mathsf{SIZE}(s)\) (fan-in-two \(\{ \wedge ,\vee \} \) gates with free negation flags on gate inputs) and \(\mathsf{P/poly}\). A circuit family has one circuit at each positive input length and a stored answer, of size \(0\), on the empty input. \(\mathsf{PromiseSIZE}(s)\) is equivalently the class of promise problems solved on both sides by one circuit family of pointwise size at most \(s\) (mem_PromiseSIZE_iff). \(\mathsf{PromiseEventuallySIZE}(s)\) asks for a family solving both sides whose size is at most \(s(n)\) for all sufficiently large \(n\). The library proves that an eventual polynomial bound already gives \(\mathsf{PromisePPoly}\) (PromiseEventuallySIZE_polynomial_subset_PromisePPoly).

For a deterministic machine \(U\) (with any number of work tapes), a string \(x\) and a clock \(t\),

with values in \(\mathbb {N} \cup \{ \infty \} \) and value \(\infty \) when no program exists. Here “produces” means halting with exact output \(x\) (Definition 11), and “within \(t\) steps” means halting after at most \(t\) transitions. No universality is assumed. A prefix-free variant \(K_U\) is defined only for machines bundled with a proof that their halting domain is prefix-free (TM.PrefixFreeMachine); it is the plain minimum \(C_U\) of the certified machine.

Levin’s \(\mathrm{Kt}_U(x) = \min \{ |p| + \lceil \log _2 t \rceil : U \text{ produces } x \text{ on } p \text{ within } t \text{ steps}\} \), and the random-access measure \(\mathrm{KT}_U(x) = \min \{ |d| + t\} \) over descriptions \(d\) from which an indexed-bit evaluator answers every query “what is bit \(i\) of \(x\)?” (including a fixed end-marker convention) within \(t\) steps. This requires an explicit random-access evaluator model and an efficient universal evaluator for it. The associated problems are \(\mathsf{MKtP}\) and \(\mathsf{MKTP}\) with a threshold, their search versions, and gap promise problems.

Fix a machine \(U\) and a threshold \(r \colon \mathbb {N} \to \mathbb {N}\). An instance \((x, 1^t)\), with \(t \ge 0\) (the empty clock is \(t = 0\)), is encoded as \(\mathrm{pair}(x, 1^t)\), and \(\mathsf{MINKT}(U, r)\) is the language of canonical codes with the strict inequality \(C^t_U(x) {\lt} r(|x|)\). Malformed strings (a failed pairing or a clock containing a \(0\)) are no-instances.

Parameters are a description loss \(\sigma (n, s)\) and a clock blow-up \(\tau (n, t)\); the promise problem takes a proof that they are widening (\(\sigma (n,s) \ge s\) and \(\tau (n,t) \ge t\) for all arguments), which makes its two sides disjoint. On canonical instances \((x, 1^t, 1^s)\), encoded as \(\mathrm{pair}(\mathrm{pair}(x, 1^t), 1^s)\), the promise \(\mathsf{GapMINKT}(U, \sigma , \tau )\) has yes side \(C^t_U(x) \le s\) and no side \(C^{\tau (|x|,t)}_U(x) {\gt} \sigma (|x|, s)\); malformed strings lie outside the promise. The exact logarithmic variant of Hirahara 2022 is Definition 493.

An instance consists of an arity \(n\), a truth table \(T \in \{ 0,1\} ^{2^n}\) (entry \(k\) is the value on the input whose bit \(j\) is bit \(j\) of \(k\), a little-endian order) and a threshold \(s\), encoded canonically as \(\mathrm{pair}(\mathrm{bin}(n), \mathrm{pair}(\mathrm{bin}(s), T))\) with minimal binary naturals; strings that are not canonical codes (including tables of the wrong length) are no-instances. For \(n {\gt} 0\) the instance is a yes-instance iff some circuit of fan-in-two \(\{ \wedge ,\vee \} \) gates with free negation flags on gate inputs and at most \(s\) gates (input vertices free, the output gate counted) computes the function with truth table \(T\). Arity-zero instances are accepted at every threshold (the size-zero convention of circuit families).

Three promise formulations, all with yes side “minimum size at most the yes threshold” and no side “minimum size strictly above the no threshold”, and all placing malformed strings outside the promise: (a) canonical instances \((n, T, s)\) with yes threshold \(s\) and no threshold \(\rho (n, s)\) for a widening relaxation \(\rho (n, s) \ge s\); (b) slices \(\mathsf{GapMCSP}[s_{\mathrm{yes}}, s_{\mathrm{no}}]\) with arity-indexed thresholds \(s_{\mathrm{yes}}(n) \le s_{\mathrm{no}}(n)\) on canonical codes whose encoded threshold equals \(s_{\mathrm{yes}}(n)\); (c) the raw slice on bare truth tables of length exactly \(N = 2^n\), as in the magnification literature. Adding and erasing the canonical metadata are proved to be side-preserving maps between (b) and (c) in both directions (GapMCSP.rawSliceProblem_mapReducesVia_rawToCanonical, GapMCSP.sliceProblem_mapReducesVia_canonicalToRaw); that these maps are in \(\mathsf{FP}\) is not yet proved.

An instance is an arity \(n\), a finite list of samples \((z_i, b_i) \in \{ 0,1\} ^n \times \{ 0,1\} \) (repetitions and contradictions allowed) and a threshold \(s\), with a canonical total codec. A canonical code is a yes-instance iff some fan-in-two \(\{ \wedge ,\vee \} \) circuit with at most \(s\) gates satisfies \(C(z_i) = b_i\) for every sample (for \(n = 0\): some constant is consistent with every sample, at every threshold). Malformed strings are no-instances.

Search-\(\mathsf{MCSP}\); linear-overhead transport of minimum size to other gate conventions; partial-function \(\mathsf{MCSP}\) (truth tables with don’t-care entries); formula, branching-program and oracle-circuit size versions; and implicit variants whose truth table is given by a circuit. Each keeps its qualifiers in its name, and results about a variant are never surfaced as statements about total \(\mathsf{MCSP}\), whose \(\mathsf{NP}\)-hardness is open.

For \(f \colon \{ 0,1\} ^n \to \{ 0,1\} \) with \(n {\gt} 0\) and a threshold \(s\), a finite list \(L \subseteq \{ 0,1\} ^n\) is an anti-checker for \((f, s)\) if every fan-in-two \(\{ \wedge ,\vee \} \) circuit with at most \(s\) gates disagrees with \(f\) on some input of \(L\).

Rational parameters are positive fractions \(a/b\) with \(a, b \ge 1\), and all roundings are explicit. For a positive rational \(\beta \) and an integer \(c \ge 1\), the raw problem at \((\beta , c)\) is the raw \(\mathsf{GapMCSP}\) slice with yes threshold \(\lfloor 2^{\lfloor \beta n \rfloor }/(cn) \rfloor \) and no threshold \(2^{\lfloor \beta n \rfloor }\) at arity \(n\). For a positive rational \(\varepsilon \), the size bound at input length \(N\) is \(2^{n + \lceil \varepsilon n \rceil }\) with \(n = \lfloor \log _2 N \rfloor \), which is the rounded \(N^{1+\varepsilon }\) at \(N = 2^n\). The hypothesis \(\mathrm{LB}(c)\) asserts: there is a positive rational \(\varepsilon \) such that for every sufficiently small positive rational \(\beta \) (that is, for all \(\beta \) at most some positive \(\beta _0\)), the raw problem at \((\beta , c)\) is not in \(\mathsf{PromiseEventuallySIZE}(N^{1+\varepsilon })\). The quantifier over small \(\beta \) is a filter at zero from above, kept separate from the eventual quantifier over input lengths.

Hamming distance, balls \(B(r)\) and their binomial volume on \(\{ 0,1\} ^n\); a set of words is \(d\)-separated when distinct words are at distance at least \(d\). A block code is an injective encoding \(\{ 0,1\} ^k \to \{ 0,1\} ^m\), with rate \(k/m\), a \(\mathrm{GF}(2)\)-linearity predicate (preserving zero and XOR), and the minimum-distance contract “distinct messages have codewords at distance at least \(d\)”. The repetition code with \(c \ge 1\) copies is a concrete \(\mathrm{GF}(2)\)-linear instance: it multiplies Hamming distance by exactly \(c\), so it has minimum distance at least \(c\), and for \(k \ge 1\) its rate is exactly \(1/c\).

A list code with messages in \(\{ 0,1\} ^k\) encodes each message as a Boolean function on a finite coordinate set and decodes each received word to an indexed list of \(L\) candidate messages; it is list-decodable up to relative distance \(\rho \) if every message whose codeword disagrees with the received word on at most a \(\rho \) fraction of coordinates appears in the list. A family of list codes is indexed by message length \(k\) and inverse accuracy \(q\), with codeword coordinates in \(\{ 0,1\} ^{\ell (k,q)}\). It is list-decodable if each code is list-decodable up to relative distance \(1/2 - 1/q\) for \(q \ge 2\); it has polynomial parameters if \(2^{\ell (k,q)} \le a(k + q + 1)^e\) and the list size is at most \(b(q+1)^f\) for constants \(a, e, b, f\); and a uniform realization is one encoder machine, printing the full truth table of the codeword, and one decoder machine, reading the full truth table of any received word and printing all \(L\) candidates, that work for all \(k, q\) on canonically framed inputs within a common time bound \(a'(k + q + 1)^{e'}\).