Zobrazeno 1 - 10
of 36
pro vyhledávání: '"Frege system"'
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Publikováno v:
UPCommons. Portal del coneixement obert de la UPC
Universitat Politècnica de Catalunya (UPC)
Universitat Politècnica de Catalunya (UPC)
We define and investigate Frege systems for quantified Boolean formulas (QBF). For these new proof systems, we develop a lower bound technique that directly lifts circuit lower bounds for a circuit class C to the QBF Frege system operating with lines
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b1a71059526abcfaa4d32b866518de6d
https://doi.org/10.1145/3381881
https://doi.org/10.1145/3381881
Autor:
Samuel R. Buss
Publikováno v:
Outstanding Contributions to Logic ISBN: 9783030714291
We discuss substitution rules that allow the substitution of formulas for formula variables. A substitution rule was first introduced by Frege. More recently, substitution is studied in the setting of propositional logic. We state theorems of Urquhar
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::1826ee7f4610e8ad7298e88a78a900f3
https://doi.org/10.1007/978-3-030-71430-7_17
https://doi.org/10.1007/978-3-030-71430-7_17
Autor:
Raheleh Jalali
In this paper, we investigate the proof complexity of a wide range of substructural systems. For any proof system $\mathbf{P}$ at least as strong as Full Lambek calculus, $\mathbf{FL}$, and polynomially simulated by the extended Frege system for some
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::aa0490ac2b040f9e05b6e5275259c407
http://arxiv.org/abs/2006.09705
http://arxiv.org/abs/2006.09705
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Autor:
Pavel Pudlák
The canonical pair of a proof system P is the pair of disjoint NP sets where one set is the set of all satisfiable CNF formulas and the other is the set of CNF formulas that have P-proofs bounded by some polynomial. We give a combinatorial characteri
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::94c6a4f52cc8f21e1500e0366d13ec1d
http://arxiv.org/abs/1912.03013
http://arxiv.org/abs/1912.03013
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Autor:
Olaf Beyersdorff, Ján Pich
Publikováno v:
LICS
Recently Beyersdorff, Bonacina, and Chew [10] introduced a natural class of Frege systems for quantified Boolean formulas (QBF) and showed strong lower bounds for restricted versions of these systems. Here we provide a comprehensive analysis of the n
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::f6fadf1d3aec6dd5235688bd355bf9b9
https://doi.org/10.1145/2933575.2933597
https://doi.org/10.1145/2933575.2933597
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Autor:
Jan Krajíček
Publikováno v:
Information Processing Letters. 112:490-493
We apply classical proof complexity ideas to transfer lengths-of-proofs lower bounds for a propositional proof system P into examples of hard unsatisfiable formulas for a class Alg(P) of SAT algorithms determined by P. The class Alg(P) contains those
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::5880571e5e23d0b4be45d507f3b6a831
https://doi.org/10.1016/j.ipl.2012.03.009
https://doi.org/10.1016/j.ipl.2012.03.009