Initial configuration constraints
ProvedPvsNP.initialCNF_correctGiven a one-symbol encoding, the initial formula is satisfied exactly when each first-row symbol is an allowed initial value.
Status: Known mathematics / implementation obligation awaiting formal proof.
import Definitions.Def_PvsNPFrontier
namespace PvsNP
theorem initialCNF_correct (S : TableauSpec) (τ : ℕ → Bool) (T : ℕ → ℕ → ℕ)
(h : TableauEncoding S τ T) :
evalCNF τ (initialCNF S) = true ↔
∀ c < tableauWidth S, T 0 c ∈ (S.initialAllowed[c]?.getD []) := 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 initial formula is true under if and only if . A missing required initial list is empty and makes the right-hand condition false; the theorem retains the encoding hypothesis in that case. 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 initial formula has, in increasing and then increasing , the negative unit clause exactly when . 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.