Naturligt bevis

I kompleksitetsteori er et naturligt bevis et lavere grænse bevis på boolske kredsløb, der tilfredsstiller visse egenskaber. Disse beviser siges at være naturlige, fordi de bruger en klassisk teknik i litteraturen i marken. De blev bragt i lyset af et resultat af Alexander Razborov og Steven Rudich, der beviser, at (under en klassisk hypotese) denne form for bevis ikke kan tillade at bevise, at P er forskellig fra NP .

Sammenhæng

Teorien om kompleksitet består især i at klassificere algoritmiske problemer efter deres vanskeligheder. De klassiske definitioner af kompleksitetsklasser , for eksempel de af klasse P og NP , overvejer de ressourcer, der er nødvendige for at løse problemet på en Turing-maskine . Men for at vise lavere grænser er det ofte lettere at overveje en anden modelberegning (in) , de boolske kredsløb . For eksempel for at bevise, at P er forskellig fra NP, er en klassisk strategi at vise, at P / poly , en kredsløbsanalog af P, ikke indeholder alle NP's problemer.

Naturlige bevis er en type lavere grænse bevis for boolske kredsløb. Disse bevis følger følgende strategi: udviser en egenskab ved et bestemt problem, således at intet kredsløb af den betragtede klasse opfylder det.

Definitioner

Givet et kredsløb klasse U , en egenskab, der er ikke opfyldt, U er en sekvens af Boolske funktioner, således at hvis en sekvens er del af en uendelighed af n , så tilhører ikke U . $(C_ {n})$ $f_n$ $C_ {n}$ $(f_ {n}) _ {n}$

Vi kan betragte dem selv som et sprog og beskrive dem ved deres sandhedstabeller . Vi siger, at det kan beregnes, hvis problemet med at genkende disse sandhedstabeller er i en kompleksitetsklasse . $C_ {n}$ $C_ {n}$ $\ Gamma$ $\ Gamma$

På den anden side siger vi, at mange funktioner tilfredsstiller en egenskab, hvis en større del af dem har den. ${\ displaystyle 2 ^ {- O (n)}}$

Endelig siges en egenskab at være -naturlig, hvis den er -beregnelig, og hvis mange funktioner tilfredsstiller den. I sammenhæng med P og NP siger vi, at det kan beregnes effektivt, hvis sproget er i P / poly, og vi taler simpelthen om naturlig egenskab for P / poly-naturlige egenskaber . $\ Gamma$ $\ Gamma$ $C_ {n}$

Naturligt bevis er det, der udviser naturlige egenskaber.

Eksempler

Bevisene, der viser, at paritetsfunktionen ikke er i klassen AC 0, er AC 0 -naturlige bevis .

Resultat af Razborov og Rudich på P og NP

Hovedsætningen for Razborov og Rudich er som følger:

Hvis der findes en naturlig egenskab, som ikke er opfyldt for nogen funktion af P / poly, eksisterer der ikke en familie af pseudo-tilfældige hårde generatorer . $C_ {n}$ ${\ displaystyle 2 ^ {n ^ {\ epsilon}}}$

Vi kan også udtrykke hypotesen ved hjælp af envejsfunktioner : hvis der findes funktioner med subeksponentiel vanskelighed, er der intet naturligt bevis.

Teoremet siger generelt, at vi befinder os i en af følgende situationer:

eller der er ingen pseudo-tilfældige- vanskelige generatorer , som anses for usandsynlige, ${\ displaystyle 2 ^ {n ^ {\ epsilon}}}$
eller P = NP, som heller ikke er flertalsopfattelsen,
Ellers er P forskellig fra NP, men klassiske bevisteknikker fungerer ikke.

Historie

Alexander Razborov og Steven Rudich vandt Gödel-prisen for deres artikel om naturlig beviser.

Noter og referencer

Timothy Y. Chow, “ HVAD ER ... et naturligt bevis? ”, Notices of the American Mathematical Society , AMS, bind. 58, nr . 11, 2011( læs online ).
Alexander A. Razborov og Steven Rudich , " Natural proofs ", Journal of Computer and System Sciences , bind. 55, nr . 1,1997, s. 24–35 ( DOI 10.1006 / jcss.1997.1494 )
(i) Sanjeev Arora og Boaz Barak , Computational Complexity: En moderne tilgang , Cambridge University Press ,2009( ISBN 0-521-42426-7 ) , kap. 23 (“Hvorfor er kredsløbets nedre grænser så vanskelige?”) , P. 430.
Jean-Paul Delahaye , “ P = NP, et million dollar problem? " ,3. april 2007.
" Gödel-prisen - 2007 " , om EATCS .