- New
-
Topics
- All Categories
- Metaphysics and Epistemology
- Value Theory
- Science, Logic, and Mathematics
- Science, Logic, and Mathematics
- Logic and Philosophy of Logic
- Philosophy of Biology
- Philosophy of Cognitive Science
- Philosophy of Computing and Information
- Philosophy of Mathematics
- Philosophy of Physical Science
- Philosophy of Social Science
- Philosophy of Probability
- General Philosophy of Science
- Philosophy of Science, Misc
- History of Western Philosophy
- Philosophical Traditions
- Philosophy, Misc
- Other Academic Areas
- Journals
- Submit material
- More
Pool resolution is NP-hard to recognize
Archive for Mathematical Logic 48 (8):793-798 (2009)
Abstract
A pool resolution proof is a dag-like resolution proof which admits a depth-first traversal tree in which no variable is used as a resolution variable twice on any branch. The problem of determining whether a given dag-like resolution proof is a valid pool resolution proof is shown to be NP-completeOther Versions
No versions found
Links
PhilArchive
External links
(no proxy)
Setup an account with your affiliations in order to access resources via your University's proxy server
Through your library
- Sign in / register and customize your OpenURL resolver
- Configure custom resolver
My notes
Similar books and articles
Minimum propositional proof length is NP-Hard to linearly approximate.Michael Alekhnovich, Sam Buss, Shlomo Moran & Toniann Pitassi - 2001 - Journal of Symbolic Logic 66 (1):171-191.
String Rewriting and Proof Complexity: an interpretation of Resolution.Stefano Cavagnetto - 2009 - Reports on Mathematical Logic:167-200.
Propositional proof compressions and DNF logic.L. Gordeev, E. Haeusler & L. Pereira - 2011 - Logic Journal of the IGPL 19 (1):62-86.
Classical Model Existence And Left Resolution.Jui-Lin Lee - 2007 - Logic and Logical Philosophy 16 (4):333-352.
Resolution calculus for the first order linear logic.Grigori Mints - 1993 - Journal of Logic, Language and Information 2 (1):59-83.
Extracting the resolution algorithm from a completeness proof for the propositional calculus.Robert Constable & Wojciech Moczydłowski - 2010 - Annals of Pure and Applied Logic 161 (3):337-348.
Resolution and the origins of structural reasoning: Early proof-theoretic ideas of Hertz and Gentzen.Peter Schroeder-Heister - 2002 - Bulletin of Symbolic Logic 8 (2):246-265.
A completeness proof for a logic with an alternative necessity operator.Stéphane Demri - 1997 - Studia Logica 58 (1):99-112.
Dual Erotetic Calculi and the Minimal LFI.Szymon Chlebowski & Dorota Leszczyńska-Jasion - 2015 - Studia Logica 103 (6):1245-1278.
Analytics
Added to PP
2013-11-23
Downloads
86 (#244,377)
6 months
22 (#137,005)
2013-11-23
Downloads
86 (#244,377)
6 months
22 (#137,005)
Historical graph of downloads
Citations of this work
Lower Bounds for resolution and cutting plane proofs and monotone computations.Pavel Pudlak - 1997 - Journal of Symbolic Logic 62 (3):981-998.
Lower Bounds for cutting planes proofs with small coefficients.Maria Bonet, Toniann Pitassi & Ran Raz - 1997 - Journal of Symbolic Logic 62 (3):708-728.
PhilPapers logo by Andrea Andrews and Meghan Driscoll.
This site uses cookies and Google Analytics (see our terms & conditions for details regarding the privacy implications). Use of this site is subject to terms & conditions.
All rights reserved by The PhilPapers Foundation
Server: philpapers-web-667477cd97-wmc4m dc2