versus : a fixed depth separating all consecutive levels
OpenFdVersusFdSucc.fd_vs_fd_succlogicproof-complexity
There is a constant such that for every there is a family of tautologies of depth at most with such that
- (quasi-polynomial upper bound) for some , each has an -proof of size at most ;
- (exponential lower bound) for some and all sufficiently large , every -proof of has size at least .
In symbols:
This is Krajíček's open problem: one extra level of proof depth gives an exponential speed-up already on tautologies of one fixed depth.
Formalization Note The problem says "for any "; since a depth- formula has no -proof when , the statement is taken for . The problem allows a polynomial or quasi-polynomial upper bound; the goal uses the weaker (quasi-polynomial) one, so a polynomial solution also proves it.
Preamble
import Definitions.Def_FdVersusFdSucc_defs open Filter
Formal statement
namespace FdVersusFdSucc
/-- **Goal** (Krajíček; Open Problem Garden "F_d versus F_{d+1}"). There is a constant `k`
such that for every `d ≥ k` there is a sequence of depth-`k` tautologies with
quasi-polynomial-size proofs in `F_{d+1}` that require exponential-size proofs in `F_d`. -/
theorem fd_vs_fd_succ :
∃ k : ℕ, ∀ d : ℕ, k ≤ d → ∃ τ : ℕ → Formula, QuasiPolySeparates k d τ := by sorry
end FdVersusFdSucc
Source
Open Problem Garden, 'F_d versus F_{d+1}' (J. Krajíček), http://www.openproblemgarden.org/op/f_d_versus_f_d_1 (problem statement); J. Krajíček, Bounded arithmetic, propositional logic, and complexity theory, CUP 1995, p. 243.
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.