Separation of from by depth- tautologies
OpenFdVersusFdSucc.krajicek_depth_dependent_separationlogicproof-complexity
There is such that for every there is a family of tautologies of depth at most with such that
- for some , each has an -proof of size at most ;
- for some and all sufficiently large , every -proof of has size at least .
This is the case of the problem in which the depth of the tautologies may depend on (with ), recorded as known on the Open Problem Garden page.
Formalization Note The statement is asked only for all sufficiently large , to be robust to the offset between depth conventions (here literals have depth ; in this convention the statement fails for , since depth-1 tautologies have linear-size -proofs).
Preamble
import Definitions.Def_FdVersusFdSucc_defs open Filter
Formal statement
namespace FdVersusFdSucc
/-- (Krajíček 1994, as recorded on the Open Problem Garden page: the problem is solved when `k`
may depend on `d`, with `k := d`.) For all sufficiently large `d` there is a sequence of
depth-`d` tautologies with polynomial-size `F_{d+1}`-proofs that require exponential-size
`F_d`-proofs. -/
theorem krajicek_depth_dependent_separation :
∃ d₀ : ℕ, ∀ d : ℕ, d₀ ≤ d → ∃ τ : ℕ → Formula, PolySeparates d d τ := by sorry
end FdVersusFdSucc
Source
J. Krajíček, Lower bounds to the size of constant-depth propositional proofs, J. Symbolic Logic 59(1), 1994, 73-86; stated as known (k := d) on Open Problem Garden, 'F_d versus F_{d+1}' (J. Krajíček), http://www.openproblemgarden.org/op/f_d_versus_f_d_1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.