Conditional SAT characterization
ProvedPvsNP.sat_characterization_from_infrastructureAssuming P inclusion, SAT membership in NP, SAT hardness and closure of P under reductions, equality of P and NP is equivalent to SAT belonging to P.
Status: Local proof checked; unpublished draft statement.
import Definitions.Def_PvsNPFrontier
namespace PvsNP
theorem sat_characterization_from_infrastructure
(hincl : P ⊆ NP) (hsat : SAT ∈ NP) (hhard : NPHard SAT)
(hclosed : ∀ A B : DecisionProblem, PReducible A B → B ∈ P → A ∈ P) :
P = NP ↔ SAT ∈ P := by sorry
end PvsNPRead-back
What the Lean code literally says, in plain math · gpt-6-astra
Assume four hypotheses: ; ; ; and . Under these supplied hypotheses, if and only if . In particular the inclusion, the checker description of , its incoming reductions, and closure of under the specified reductions are premises of this theorem rather than claims established by its statement. Here , is the set of all finite Boolean lists, including the empty list, and is list length. The set consists exactly of languages for which there is a Boolean function satisfying and . The set consists exactly of languages for which there exist and satisfying and . This includes and empty input: , whereas for . Write for existence of such a machine and a polynomial that, for every , compute the singleton output from input in at most steps. Write for existence of such a machine and a polynomial that, for all , compute in at most steps from the list obtained by tagging every bit of with the left injection into , tagging every bit of with the right injection, and concatenating those two lists. For languages , write to mean that there exists satisfying and . Write for existence of such a machine and a polynomial that, for every , compute output list from input list in at most steps. Different existential computation witnesses may use different machines and polynomials. A machine in these assertions is a Mathlib TM2 stack machine with finitely many stack indices, instruction labels, and control states, a finite input-stack alphabet, designated input and output stacks, a program, and initial label and control state; its other stack alphabets need not be finite. Input and output alphabet bijections transport the specified encoded lists to the corresponding stack alphabets. Computation starts with only the input stack populated, and reaches a halted configuration with the specified output on the output stack, all other stacks empty, and the control state reset to its initial value. Time counts executions of whole TM2 statements, each of which may contain several stack operations. The language consists of exactly those for which there are a formula and an assignment such that and every clause of is true under ; strings without such an encoding are excluded. 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 . 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.