REVIEWS-Minimum propositional proof length is NP-hard to linearly approximate

&
Bulletin of Symbolic Logic 8 (2):301-301 (2002)
  Copy   BIBTEX

Abstract

This article has no associated abstract. (fix it)

Categories

Keywords

Reprint years

DOI

10.2307/2693969

Links

PhilArchive



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

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

Review: Michael Alekhnovich, Sam Buss, Shlomo Moran, Toniann Pitassi, Minimum Propositional Proof Length Is NP-Hard to Linearly Approximate. [REVIEW]Alexander Razborov - 2002 - Bulletin of Symbolic Logic 8 (2):301-302.
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.
Some remarks on lengths of propositional proofs.Samuel R. Buss - 1995 - Archive for Mathematical Logic 34 (6):377-394.
Propositional proof systems, the consistency of first order theories and the complexity of computations.Jan Krajíček & Pavel Pudlák - 1989 - Journal of Symbolic Logic 54 (3):1063-1079.
The deduction rule and linear and near-linear proof simulations.Maria Luisa Bonet & Samuel R. Buss - 1993 - Journal of Symbolic Logic 58 (2):688-709.
Reasoning processes in propositional logic.Claes Strannegård, Simon Ulfsbäcker, David Hedqvist & Tommy Gärling - 2010 - Journal of Logic, Language and Information 19 (3):283-314.
Pool resolution is NP-hard to recognize.Samuel R. Buss - 2009 - Archive for Mathematical Logic 48 (8):793-798.
An unexpected separation result in Linearly Bounded Arithmetic.Arnold Beckmann & Jan Johannsen - 2005 - Mathematical Logic Quarterly 51 (2):191-200.
The complexity of propositional proofs.Nathan Segerlind - 2007 - Bulletin of Symbolic Logic 13 (4):417-481.
Proof-finding Algorithms for Classical and Subclassical Propositional Logics.M. W. Bunder & R. M. Rizkalla - 2009 - Notre Dame Journal of Formal Logic 50 (3):261-273.
A proof of axiomatizability of łukasiewicz’s three-valued implicational propositional calculus.T. Prucnal - 1967 - Studia Logica 20 (1):144-144.
Local Complexity Adaptable Trajectory Partitioning via Minimum Message Length.Charles R. Twardy - 2011 - In 18th IEEE International Conference on Image Processing. IEEE.
On the complexity of Gödel's proof predicate.Yijia Chen & Jörg Flum - 2010 - Journal of Symbolic Logic 75 (1):239-254.

Analytics

Added to PP
2014-03-24

Downloads
15 (#938,320)

6 months
8 (#350,876)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references