[图书][B] First-order logic and automated theorem proving
M Fitting - 2012 - books.google.com
There are many kinds of books on formal logic. Some have philosophers as their intended
audience, some mathematicians, some computer scien tists. Although there is a common …
audience, some mathematicians, some computer scien tists. Although there is a common …
[图书][B] Boolean function complexity: advances and frontiers
S Jukna - 2012 - Springer
Boolean circuit complexity is the combinatorics of computer science and involves many
intriguing problems that are easy to state and explain, even for the layman. This book is a …
intriguing problems that are easy to state and explain, even for the layman. This book is a …
Contributions to the theory of practical quantified Boolean formula solving
A Van Gelder - International Conference on Principles and Practice of …, 2012 - Springer
Recent solvers for quantified boolean formulas (QBFs) use a clause learning method based
on a procedure proposed by Giunchiglia et al.(JAIR 2006), which avoids creating …
on a procedure proposed by Giunchiglia et al.(JAIR 2006), which avoids creating …
On the virtue of succinct proofs: Amplifying communication complexity hardness to time-space trade-offs in proof complexity
T Huynh, J Nordstrom - Proceedings of the forty-fourth annual ACM …, 2012 - dl.acm.org
An active line of research in proof complexity over the last decade has been the study of
proof space and trade-offs between size and space. Such questions were originally …
proof space and trade-offs between size and space. Such questions were originally …
Towards NP–P via proof complexity and search
SR Buss - Annals of Pure and Applied Logic, 2012 - Elsevier
This is a survey of work on proof complexity and proof search from a logico-algorithmic
viewpoint, as motivated by the P versus NP problem. We discuss propositional proof …
viewpoint, as motivated by the P versus NP problem. We discuss propositional proof …
Relating proof complexity measures and practical hardness of SAT
Boolean satisfiability (SAT) solvers have improved enormously in performance over the last
10–15 years and are today an indispensable tool for solving a wide range of computational …
10–15 years and are today an indispensable tool for solving a wide range of computational …
Extension without cut
L Straßburger - Annals of Pure and Applied Logic, 2012 - Elsevier
In proof theory one distinguishes sequent proofs with cut and cut-free sequent proofs, while
for proof complexity one distinguishes Frege systems and extended Frege systems. In this …
for proof complexity one distinguishes Frege systems and extended Frege systems. In this …
A history of natural deduction
FJ Pelletier, AP Hazen - Handbook of the History of Logic, 2012 - Elsevier
Work that is called 'natural deduction'is carried out in two ways: first, as an object-language
method to prove theorems and to demonstrate the validity of arguments; and secondly, as a …
method to prove theorems and to demonstrate the validity of arguments; and secondly, as a …
Parameterized bounded-depth Frege is not optimal
A general framework for parameterized proof complexity was introduced by Dantchev et
al.[2007]. There, the authors show important results on tree-like Parameterized Resolution …
al.[2007]. There, the authors show important results on tree-like Parameterized Resolution …
On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography
The existence of an optimal propositional proof system is a major open question in proof
complexity; many people conjecture that such systems do not exist. Krajíček and Pudlák (J …
complexity; many people conjecture that such systems do not exist. Krajíček and Pudlák (J …