Domination of quadratic plus linear terms by a quadratic bound
ProvedCookLevin.quad_linear_le_quadalgebracost-modelmonotonicityquadratic-time
For all non-negative coefficients and any length , the sum of a quadratic term and a linear term is dominated by a pure quadratic term with summed coefficients:
Expanding the right-hand side via distributivity yields . The inequality then reduces to . Since , we have , and multiplying by preserves the inequality.
This algebraic bound allows bounding the composite runtime of a two-stage Turing machine (quadratic transformation followed by linear sweep) by a single quadratic cost.
Preamble
import Definitions.Def_CookLevin_Cost
Formal statement
namespace CookLevin
theorem quad_linear_le_quad (c1 c2 n : Nat) :
c1 * (n + 1) ^ 2 + c2 * (n + 1) ≤ (c1 + c2) * (n + 1) ^ 2 := by sorry
end CookLevinSource