Tableau boundary constraints
ProvedPvsNP.boundaryCNF_correctGiven a one-symbol encoding, the boundary formula is satisfied exactly when both boundary columns are zero at every row.
Status: Known mathematics / implementation obligation awaiting formal proof.
import Definitions.Def_PvsNPFrontier
namespace PvsNP
theorem boundaryCNF_correct (S : TableauSpec) (τ : ℕ → Bool) (T : ℕ → ℕ → ℕ)
(h : TableauEncoding S τ T) :
evalCNF τ (boundaryCNF S) = true ↔
∀ t ≤ S.steps, T t 0 = 0 ∧ T t (S.interior + 1) = 0 := by sorry
end PvsNPRead-back
What the Lean code literally says, in plain math · gpt-6-astra
For every specification , assignment , and total function , assume the encoding condition described here. Under that hypothesis, every clause of the boundary formula is true under if and only if . This includes both boundary columns at row zero even when or . Here has , a list of lists of natural numbers, a list of natural numbers, and a list of lists of natural numbers, with no validity restrictions on these fields. Put , , and . The list is the zero-based th list of , or the empty list when that entry is missing. The encoding condition for and is the conjunction of and . Values of outside this rectangle and Boolean values not constrained by these displayed indices are unrestricted. The boundary formula has, for each in order, the two positive unit clauses at and , in that order. A formula is a finite list of clauses, each clause a finite list of literals . Under an assignment , the literal is true exactly when , a clause is true exactly when some literal in it is true, and a formula is true exactly when every clause is true. Thus an empty clause is false and an empty formula is true. Here , is the set of all finite Boolean lists, including the empty list, and is list length. The supplied body is admitted with sorry; no proof of this assertion is supplied there.