Propoziční důkazní systém - Propositional proof system
v výrokový kalkul a složitost důkazu A výrokový systém (pps), také nazývaný a Cook – Reckhow propoziční důkazní systém, je systém pro dokazování klasický propoziční tautologie.
Matematická definice
Formálně je pps a polynomiální čas funkce P jehož rozsah je sada všech výrokových tautologií (označených TAUT).[1] Li A je vzorec, pak libovolný X takhle P(X) = A se nazývá a P-důkaz A. Podmínku definující pps lze rozdělit následovně:
- Úplnost: každý výrok tautologie má P-důkaz,
- Zdravost: má-li výrokový vzorec a P-odolný, pak je to tautologie,
- Účinnost: P běží dovnitř polynomiální čas.
Obecně platí, že systém kontroly pro jazyk L je funkce polynomu a času, jejíž rozsah je L. Propoziční systém důkazů je tedy systémem důkazů pro TAUT.
Někdy se uvažuje o následující alternativní definici: pps je uveden jako algoritmus ověření důkazu P(A,X) se dvěma vstupy. Li P přijímá pár (A,X) říkáme to X je P-důkaz A. P je vyžadován pro běh v polynomiálním čase a navíc to musí platit A má P-odolný, pouze pokud se jedná o tautologii.
Li P1 je tedy podle první definice pps P2 definován P2(A,X) právě tehdy P1(X) = A je pps podle druhé definice. Naopak, pokud P2 je tedy podle druhé definice pps P1 definován
(P1 bere páry jako vstup) je pps podle první definice, kde je pevná tautologie.
Algoritmická interpretace
Druhou definici lze považovat za nedeterministický algoritmus pro řešení členství v TAUT. To znamená, že prokázání dolní meze velikosti superpolynomiálního důkazu pro pps by vyloučilo existenci určité třídy algoritmů polynomiálního času založených na těchto pps.
Jako příklad lze uvést, že exponenciální velikost důkazu má dolní hranice rozlišení pro princip holubí díry naznačují, že jakýkoli algoritmus založený na rozlišení nemůže efektivně rozhodnout TAUT nebo SAT a selže dále princip holubí díry tautologie. To je významné, protože třída algoritmů založená na rozlišení zahrnuje většinu současných výrokových algoritmů pro hledání důkazů a moderní průmyslové SAT řešení.
Dějiny
Historicky, Fregeův výrokový počet byl prvním výrokovým důkazním systémem. Obecná definice systému propozičního dokazování je způsobena Stephen Cook a Robert A. Reckhow (1979).[1]
Vztah s teorií výpočetní složitosti
Systém propozičních důkazů lze porovnat pomocí pojmu p-simulace. Propoziční systém důkazů P p-simuluje Q (psáno jako P ≤pQ) když existuje funkce polynomiálního času F takhle P(F(X)) = Q(X) pro každého X.[1] To znamená, že Q-důkaz X, můžeme najít v polynomiálním čase a P- odolný vůči stejné tautologii. Li P ≤pQ a Q ≤pP, kontrolní systémy P a Q jsou p-ekvivalent. Existuje také slabší pojem simulace: a pps P simuluje nebo slabě p-simuluje pps Q pokud existuje polynom p tak, že pro každého Q-důkaz X tautologie A, tady je P-důkaz y z A taková, že délka y, |y| je nanejvýš p(|X|). (Někteří autoři používají slova p-simulace a simulace zaměnitelně pro jeden z těchto dvou konceptů, obvykle druhý.)
Nazývá se systém propozičních důkazů p-optimální Pokud si to p-imuluje všechny ostatní systémy propozičních důkazů a je optimální pokud simuluje všechny ostatní pps. Propoziční systém důkazů P je polynomiálně ohraničené (také nazývané super), pokud má každá tautologie krátkou (tj. polynomickou velikost) P-důkaz.
Li P je polynomiálně ohraničený a Q simuluje P, pak Q je také polynomiálně ohraničený.
Soubor výrokových tautologií, TAUT, je a coNP -kompletní set. Propozičním důkazním systémem je ověřovatel certifikátu pro členství v TAUT. Existence polynomiálně ohraničeného systému propozičních důkazů znamená, že existuje ověřovatel s certifikáty polynomiální velikosti, tj. TAUT je v NP. Ve skutečnosti jsou tyto dva výroky rovnocenné, tj. Existuje polynomiálně ohraničený systém propozičních důkazů právě tehdy, když třídy složitosti NP a coNP jsou rovny.[1]
Některé třídy rovnocennosti důkazních systémů v rámci simulace nebo p-imulace úzce souvisí s teoriemi omezená aritmetika; jsou to v podstatě „nejednotné“ verze omezené aritmetiky, stejně jako třídy obvodů jsou nejednotné verze tříd složitosti založených na prostředcích. Systémy „Extended Frege“ (umožňující zavádění nových proměnných podle definice) odpovídají tímto způsobem například polynomiálně ohraničeným systémům. Tam, kde omezená aritmetika zase odpovídá třídě složitosti založené na obvodech, existují často podobnosti mezi teorií důkazních systémů a teorií obvodových rodin, jako je shoda výsledků s dolní mezí a separací. Například stejně jako počítání nelze provést pomocí řada obvodů subexponenciální velikosti, mnoho tautologií vztahujících se k princip pigeonhole nemůže mít podexponenciální důkazy v systému důkazů založeném na vzorcích s omezenou hloubkou (a zejména ne systémy založenými na rozlišení, protože se spoléhají pouze na vzorce hloubky 1).
Příklady propozičních důkazních systémů
Některé příklady studovaných systémů propozičních důkazů:
- Výrokové Rozlišení a různá omezení a rozšíření Algoritmus DPLL
- Přirozený odpočet
- Sekvenční počet
- Frege systém
- Rozšířený systém Frege
- Polynomiální počet
- Systém Nullstellensatz
- Metoda roviny řezu
Reference
Další čtení
- Samuel Buss (1998), „An Introduction to proof theory“, in: Příručka teorie důkazů (ed. S.R. Buss), Elsevier (1998).
- P. Pudlák (1998), "Délka důkazů ", in: Handbook of Proof Theory (ed. S.R.Buss), Elsevier, (1998).
- P. Beame a T. Pitassi (1998). Složitost výroků: minulost, přítomnost a budoucnost. Technická zpráva TR98-067, Elektronické kolokvium o výpočetní složitosti.
- Nathan Segerlind (2007) „Složitost výroků“, Bulletin of Symbolic Logic 13 (4): 417–481
- J. Krajíček (1995), Omezená aritmetika, výroková logika a teorie složitosti, Cambridge University Press.
- J. Krajíček, Složitost důkazu, v: Proc. 4. místo Evropský kongres matematiky (ed. A. Laptev), EMS, Curych, str. 221–231, (2005).
- J. Krajíček, Složitost důkazního důkazu I. a Složitost důkazu a aritmetika.
- Stephen Cook a Phuong Nguyen, Logické základy složitosti důkazů, Cambridge University Press, 2010 (návrh z roku 2008 )
- Robert Reckhow, O délkách důkazů v propozičním počtu, Disertační práce, 1975.