Nous prouvons NP ≠ P dans ZF. Nous définissons une relation Δ₀ Silence (i, p, n): la machine de Turing à horloge Mᵢ avec oracle p s’exécute en n étapes sans interroger aucun indice j ∈ dom (p). Nous prouvons dans ZF le Principe du Silence: ∀e∈ω ∀p∈ℙ ∃n∈ω n > nₚ ∧ (∀i<e) Silence (i, p, n). En itérant ce principe, nous construisons un langage Δ₁ explicite p∞ ∈ NP tel que toute machine à temps polynomial borné diffère de p∞ sur une entrée. Ainsi ZF ⊢ p∞ ∈ NP ∖ P, et donc ZF ⊢ NP ≠ P. La construction est finitaire, effective, et prouvablement non-relativisante, contournant ainsi la barrière de Baker–Gill–Solovay. La séparation est Σ₂⁰ et donc absolue pour le modèle standard de l’arithmétique. Note de révision: Cette v2 remplace toutes les versions antérieures. Elle corrige la preuve du Lemme 4. 1 en utilisant kᵢ ≤ i issu de l’énumération des machines à horloge, et ajoute le Corollaire 5. 2 sur la non-relativisation pour répondre explicitement à la barrière BGS. Le Théorème 3. 1 et le résultat principal ZF ⊢ NP ≠ P sont inchangés.
Jean Florent Romaric GNAYORO (Wed,) studied this question.