Název: Metody odhadů složitosti důkazů ve výrokové logice
Překlad názvu: Methods of proving lower bounds in propositional logic
Autoři: Peterová, Alena ; Pudlák, Pavel (vedoucí práce) ; Krajíček, Jan (oponent)
Typ dokumentu: Diplomové práce
Rok: 2013
Jazyk: cze
Abstrakt: [cze] [eng]
V této práci se věnujeme složitosti důkazových systémů pro výrokovou logiku. Nejprve ukážeme exponenciální dolní odhad na složitost rezoluce přímou aplikací Razborovovy aproximační metody, která byla dosud používána pouze pro odhady na velikost monotónních obvodů. Následně použijeme aproximační metodu i pro nový důkaz exponenciálního dolního odhadu na složitost náhodných rezolučních důkazů. To by mělo mít další využití při separování různých teorií v omezené aritmetice. V obou případech využijeme problém z teorie grafů zvaný Broken Mosquito Screens. Na závěr vyslovíme hypotézu, že aproximační metoda bude mít využití i v silnějších důkazových systémech, jako například Cutting Planes. Powered by TCPDF (www.tcpdf.org) In the present work, we study the propositional proof complexity. First, we prove an exponential lower bound on the complexity of resolution applying directly Razborov's approximation method, which was previously used only for bounds on the size of monotone circuits. Next, we use the approximation method for a new proof of an exponential lower bound on the complexity of random resolution refutations. That should have further applications in separating some theories in bounded arithmetic. In both cases, we use a problem from the graph theory called Broken Mosquito Screens. Finally, we state a conjecture that the approximation method is applicable even for stronger propositional proof systems, for example Cutting Plane Proofs. Powered by TCPDF (www.tcpdf.org)
Klíčová slova: aproximační metoda; Broken Mosquito Screens; důkazová složitost; Rezoluce; approximation method; Broken Mosquito Screens; proof complexity; Resolution

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/52080

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-321397


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Diplomové práce