Class inequality is strict containment, given inclusion
ProvedPvsNP.P_ne_NP_iff_strictAssuming P is contained in NP, their inequality is equivalent to P being a proper subset of NP.
Status: Local proof checked; unpublished draft statement.
import Definitions.Def_PvsNPFrontier namespace PvsNP theorem P_ne_NP_iff_strict (h : P ⊆ NP) : P ≠ NP ↔ P ⊂ NP := by sorry end PvsNP
Read-back
What the Lean code literally says, in plain math · gpt-6-astra
Assume . Under precisely this inclusion hypothesis, if and only if , where the strict inclusion means and the reverse inclusion fails. The hypothesis is supplied to the theorem rather than proved 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. 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.