Přirozený důkaz - Natural proof

v teorie výpočetní složitosti, a přirozený důkaz je určitým druhem důkazu, který ho potvrzuje třída složitosti se liší od jiného. I když jsou tyto důkazy v jistém smyslu „přirozené“, lze je ukázat (za předpokladu široce věřeného dohadu o existenci pseudonáhodné funkce ), že žádný takový důkaz nelze použít k vyřešení Problém P vs. NP.

Přehled

Pojem přirozené důkazy zavedl Alexander Razborov a Steven Rudich ve svém článku „Přírodní důkazy“, který byl poprvé představen v roce 1994 a později publikován v roce 1997, za který obdrželi rok 2007 Gödelova cena.[1]

Konkrétně přírodní důkazy dokazují nižší meze pro složitost obvodu z booleovské funkce. Přirozený důkaz ukazuje, ať už přímo nebo nepřímo, že booleovská funkce má určité přirozená kombinatorická vlastnost. Za předpokladu, že pseudonáhodné funkce existují s „exponenciální tvrdostí“, jak je uvedeno v jejich hlavní větě, Razborov a Rudich ukazují, že tyto důkazy nemohou oddělit určité třídy složitosti. Je pozoruhodné, že za předpokladu, že existují pseudonáhodné funkce, tyto důkazy nemohou oddělit třídy složitosti P a NP.[2]

Například v jejich článku se uvádí:

[...] zvažte běžně předpokládanou důkazní strategii pro prokázání P ≠ NP:
  • Formulujte nějaký matematický pojem „nesrovnalosti“ nebo „rozptylu“ nebo „variace“ hodnot booleovské funkce nebo přidruženého mnohostoru nebo jiné struktury. [...]
  • Indukčním argumentem ukažte, že obvody o velikosti polynomu mohou počítat pouze funkce „nízké“ odchylky. [...]
  • Tak to ukažte SAT, nebo nějaká jiná funkce v NP, má „vysoký“ rozpor.
Důkazem toho je naše hlavní věta v části 4 žádná důkazní strategie v tomto směru nemůže nikdy uspět.

Vlastnost booleovských funkcí je definována jako přírodní pokud obsahuje vlastnost splňující podmínky konstruktivity a velkorysosti definované Razborovem a Rudichem. Zhruba řečeno, podmínka konstruktivity vyžaduje, aby byla vlastnost rozhodnutelná v (kvazi) polynomiálním čase, když 2n- velikost pravdivostní tabulka z n-input boolean funkce je zadána jako vstup, asymptoticky jako n zvyšuje. To je stejné jako čas samostatně exponenciální v n. Vlastnosti, které lze snadno pochopit, pravděpodobně splní tuto podmínku. Podmínka velikosti vyžaduje, aby vlastnost obsahovala dostatečně velký zlomek množiny všech booleovských funkcí.

Vlastnost je užitečný proti třídě složitosti C pokud každá posloupnost booleovských funkcí majících vlastnost nekonečně často definuje jazyk mimo C. A přirozený důkaz je důkaz, který prokazuje, že určitý jazyk leží mimo C a označuje přirozenou vlastnost, proti které je užitečné C.

Razborov a Rudich uvádějí řadu příkladů dolně vázaných důkazů proti třídám C menší než P / poly které lze „naturalizovat“, tj. převést na přirozené důkazy. Důležitý příklad pojednává o důkazech, že problém parity není ve třídě AC0. Poskytují přesvědčivé důkazy, že techniky použité v těchto důkazech nelze rozšířit tak, aby vykazovaly silnější dolní meze. Zejména AC0-přirozené důkazy nemohou být užitečné proti AC0[m].

Razborov a Rudich také reprodukují bezpodmínečný důkaz Avi Wigdersona, že přirozené důkazy nemohou prokázat exponenciální dolní hranice pro diskrétní logaritmus problém.

V současné době existuje silné přesvědčení, že mechanismus tohoto článku ve skutečnosti blokuje důkazy dolní hranice proti třídě složitosti TC0 prahových obvodů s konstantní hloubkou a polynomem, o kterých se věří, ale neprokázaly se menší než P / poly.[3] Tato víra je proto, že podle široce věřených domněnek týkajících se tvrdosti factoring v určitých skupinách eliptických křivek, existují exponenciálně tvrdé pseudonáhodné funkce vypočítatelné v TC0.[4] Někteří vědci se však domnívají, že Razborov-Rudichova omezení jsou ve skutečnosti dobrým vodítkem pro to, co může zahrnovat „nadpřirozený“ důkaz dolní meze, jako jsou vlastnosti tvrdé nebo úplné pro exponenciální prostor.[5]

Poznámky

  1. ^ „Cena Gödel ACM-SIGACT 2007“. Archivovány od originál dne 03.03.2016. Citováno 2014-08-11.
  2. ^ A. A. Razborov a S. Rudich (1997). "Přirozené důkazy". Journal of Computer and System Sciences. 55: 24–35. doi:10.1006 / jcss.1997.1494. (Návrh )
  3. ^ https://complexityzoo.uwaterloo.ca/Complexity_Zoo:T#tc0
  4. ^ http://dl.acm.org/citation.cfm?id=972643
  5. ^ K. Regan (říjen 2002). „Porozumění přístupu Mulmuley-Sohoni k P vs. NP“ (PDF). Bulletin Evropské asociace pro teoretickou informatiku. 78: 86–97.

Reference