Constant numeric bounded-expression machine
ProvedCookLevin.boundedExpr_num_machinecliquecook-levinnp-completenesswordram
Decomposition child of CookLevin.boundedExpr_test_turingMachine_polynomial (22e0a9d5): the constant-numeric-expression instance. For a fixed numeral expression e = .num n, test e x y is the constant boolean decide (n ≠ 0) (evaluation under the empty numeric environment), so it is decided by a constant well-formed finite-alphabet multitape machine writing the verdict bit in O(1) steps, polynomially bounded by polyBound c d (x.length + y.length).
Preamble
import Definitions.Def_CookLevin_Cost import Definitions.Def_CookLevin_BoundedExpr
Formal statement
namespace CookLevin
theorem boundedExpr_num_machine (n : Nat) :
∃ (M : CookLevin.Machine) (k G c d : Nat),
CookLevin.TuringMachine k G M ∧
∀ (x y : List Bool),
CookLevin.DecidesIn M k
(CookLevin.boolsToSymbols x) (CookLevin.boolsToSymbols y)
(CookLevin.polyBound c d (x.length + y.length))
(CookLevin.BoundedExpr.test (CookLevin.BoundedExpr.num n) x y) := by
sorry
end CookLevin
Source
Richard M. Karp, Reducibility Among Combinatorial Problems, Complexity of Computer Computations, Plenum Press, pp. 85–103, 1972. https://doi.org/10.1007/978-1-4684-2001-2_9 . Main Theorem, problem 3 (CLIQUE), p. 94: membership in NP. Decomposition child of CookLevin.boundedExpr_test_turingMachine_polynomial (22e0a9d5-d4cf-4db5-836c-e5478d836f54), per-constructor instance e = .num n.