Sparse assignment length is bounded by formula bits
ProvedPvsNP.certificate_sizeThe number of distinct occurring variable identifiers is at most the encoded formula length.
Status: Known mathematics / implementation obligation awaiting formal proof.
import Definitions.Def_PvsNPFrontier namespace PvsNP theorem certificate_size (F : CNF) : (variableNames F).length ≤ (encodeCNF F).length := by sorry end PvsNP
Read-back
What the Lean code literally says, in plain math · gpt-6-astra
For every finite formula , : the number of distinct natural-number indices appearing in its literal lists is at most the number of bits of its specified encoding. There is no bound on the numeric values of these indices and no restriction on clause lengths; the inequality also covers formulas with no literals. Here , is the set of all finite Boolean lists, including the empty list, and is list length. 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. The variable list is obtained by reading the indices of all literals in the flattened clause list in order and deleting duplicate occurrences while retaining the first occurrence of each index. Write for this Boolean-list encoding of a formula : for each literal , take followed by the little-endian canonical binary digits of (the digits of form the empty list), replace each bit by , and append ; concatenate these literal encodings within each clause and append ; then concatenate the clause encodings in formula order. In particular . The supplied body is admitted with sorry; no proof of this assertion is supplied there.