Results 1 to 10 of about 1,041,561 (160)
Proof Complexity of Modal Resolution [PDF]
Journal of Automated Reasoning, 2021 AbstractWe investigate the proof complexity of modal resolution systems developed by Nalon and Dixon (J Algorithms 62(3–4):117–134, 2007) and Nalon et al. (in: Automated reasoning with analytic Tableaux and related methods—24th international conference, (TABLEAUX’15), pp 185–200, 2015), which form the basis of modal theorem proving (Nalon et al., in ...
Sarah Sigley, Olaf Beyersdorff
openaire +3 more sources
Proof Complexity Meets Algebra [PDF]
ACM Transactions on Computational Logic, 2017 We analyse how the standard reductions between constraint satisfaction problems affect their proof complexity. We show that, for the most studied propositional and semi-algebraic proof systems, the classical constructions of pp-interpretability ...
Atserias, Albert, Ochremiak, Joanna
core +12 more sources
On the relative proof complexity of deep inference via atomic flows [PDF]
Logical Methods in Computer Science, 2015 We consider the proof complexity of the minimal complete fragment, KS, of standard deep inference systems for propositional logic. To examine the size of proofs we employ atomic flows, diagrams that trace structural changes through a proof but ignore ...
Anupam Das
doaj +5 more sources
Certified Context-Free Parsing: A formalisation of Valiant's Algorithm in Agda [PDF]
Logical Methods in Computer Science, 2016 Valiant (1975) has developed an algorithm for recognition of context free languages. As of today, it remains the algorithm with the best asymptotic complexity for this purpose.
Jean-Philippe Bernardy, Patrik Jansson
doaj +4 more sources
Circuit complexity, proof complexity, and polynomial identity testing [PDF]
2014 IEEE 55th Annual Symposium on Foundations of Computer Science, 2014 We introduce a new algebraic proof system, which has tight connections to (algebraic) circuit complexity. In particular, we show that any super-polynomial lower bound on any Boolean tautology in our proof system implies that the permanent does not have ...
Grochow, Joshua A., Pitassi, Toniann
core +4 more sources
Safe Recursion on Notation into a Light Logic by Levels [PDF]
Electronic Proceedings in Theoretical Computer Science, 2010 We embed Safe Recursion on Notation (SRN) into Light Affine Logic by Levels (LALL), derived from the logic L4. LALL is an intuitionistic deductive system, with a polynomial time cut elimination strategy.
Luca Roversi, Luca Vercelli
doaj +6 more sources
Approximability and proof complexity [PDF]
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2012 This work is concerned with the proof-complexity of certifying that optimization problems do \emph{not} have good solutions. Specifically we consider bounded-degree "Sum of Squares" (SOS) proofs, a powerful algebraic proof system introduced in 1999 by ...
O'Donnell, Ryan, Zhou, Yuan
core +2 more sources
Proof Complexity of Propositional Default Logic [PDF]
Archive for Mathematical Logic, 2010 Default logic is one of the most popular and successful formalisms for non-monotonic reasoning. In 2002, Bonatti and Olivetti introduced several sequent calculi for credulous and skeptical reasoning in propositional default logic.
Beyersdorff, O +4 more
core +9 more sources
Proof complexity lower bounds from algebraic circuit complexity [PDF]
, 2016 We give upper and lower bounds on the power of subsystems of the Ideal Proof System (IPS), the algebraic proof system recently proposed by Grochow and Pitassi, where the circuits comprising the proof come from various restricted algebraic circuit classes.
Forbes, Michael +3 more
core +9 more sources
A Finite-Model-Theoretic View on Propositional Proof Complexity [PDF]
Logical Methods in Computer Science, 2022 We establish new, and surprisingly tight, connections between propositional proof complexity and finite model theory. Specifically, we show that the power of several propositional proof systems, such as Horn resolution, bounded-width resolution, and the ...
Erich Grädel +3 more
doaj +1 more source