Towards NP – P via proof complexity and search

Annals of Pure and Applied Logic 163 (7):906-917 (2012)
  Copy   BIBTEX

Abstract

This article has no associated abstract. (fix it)

Categories

Keywords

Reprint years

DOI

10.1016/j.apal.2011.09.009

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,672

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Pool resolution is NP-hard to recognize.Samuel R. Buss - 2009 - Archive for Mathematical Logic 48 (8):793-798.
Intuitionistic Logic Freed of All Metarules.Giovanna Corsi & Gabriele Tassi - 2007 - Journal of Symbolic Logic 72 (4):1204 - 1218.
Structured Pigeonhole Principle, Search Problems and Hard Tautologies.Jan Krajíček - 2005 - Journal of Symbolic Logic 70 (2):619 - 630.
Proof Complexity and Textual Cohesion.Eli Dresner - 2015 - Journal of Logic, Language and Information 24 (1):53-64.
Cut-elimination and proof-search for bi-intuitionistic logic using nested sequents.Rajeev Goré, Linda Postniece & Alwen Tiu - 1998 - In Marcus Kracht, Maarten de Rijke, Heinrich Wansing & Michael Zakharyaschev (eds.), Advances in Modal Logic. CSLI Publications. pp. 43-66.
Time complexity of a proof–search procedure for k4.Toshimasa Matsumoto - 2003 - Bulletin of the Section of Logic 32 (4):201-211.
The complexity of propositional proofs.Nathan Segerlind - 2007 - Bulletin of Symbolic Logic 13 (4):417-481.
The complexity of propositional proofs.Alasdair Urquhart - 1995 - Bulletin of Symbolic Logic 1 (4):425-467.
The cost of a cycle is a square.A. Carbone - 2002 - Journal of Symbolic Logic 67 (1):35-60.
Bounded arithmetic, proof complexity and two papers of Parikh.Samuel R. Buss - 1999 - Annals of Pure and Applied Logic 96 (1-3):43-55.
Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem.Neil Thapen - 2011 - Archive for Mathematical Logic 50 (7):665-680.
A Shell for Generic Interactive Proof Search.Aleksey Novodvorsky & Aleksey Smirnov - 1998 - Journal of Applied Non-Classical Logics 8 (1-2):123-140.
Interactive and probabilistic proof-checking.Luca Trevisan - 2000 - Annals of Pure and Applied Logic 104 (1-3):325-342.
Representation operators and computation.Brendan Kitts - 1999 - Minds and Machines 9 (2):223-240.
Proof Theory and Complexity.Carlo Cellucci - 1985 - Synthese 62 (2):173-189.

Analytics

Added to PP
2013-10-27

Downloads
50 (#316,816)

6 months
6 (#509,130)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Justification as ignorance and logical omniscience.Daniel Waxman - 2022 - Asian Journal of Philosophy 1 (1):1-8.

Add more citations

References found in this work

View all 26 references / Add more references