Review: Michael Alekhnovich, Sam Buss, Shlomo Moran, Toniann Pitassi, Minimum Propositional Proof Length Is NP-Hard to Linearly Approximate [Book Review]

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

Abstract

This article has no associated abstract. (fix it)

Categories

Keywords

Reprint years

DOI

10.2178/bsl/1182353876

Links

PhilArchive



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

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

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.
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.
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 Complexity of Resolution Refinements.Joshua Buresh-Oppenheim & Toniann Pitassi - 2007 - Journal of Symbolic Logic 72 (4):1336 - 1352.
Lower Bounds for cutting planes proofs with small coefficients.Maria Bonet, Toniann Pitassi & Ran Raz - 1997 - Journal of Symbolic Logic 62 (3):708-728.
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.
Polynomial size proofs of the propositional pigeonhole principle.Samuel R. Buss - 1987 - Journal of Symbolic Logic 52 (4):916-927.
On gödel's theorems on lengths of proofs I: Number of lines and speedup for arithmetics.Samuel R. Buss - 1994 - Journal of Symbolic Logic 59 (3):737-756.
The complexity of propositional proofs.Nathan Segerlind - 2007 - Bulletin of Symbolic Logic 13 (4):417-481.
Local Complexity Adaptable Trajectory Partitioning via Minimum Message Length.Charles R. Twardy - 2011 - In 18th IEEE International Conference on Image Processing. IEEE.
Strong isomorphism reductions in complexity theory.Sam Buss, Yijia Chen, Jörg Flum, Sy-David Friedman & Moritz Müller - 2011 - Journal of Symbolic Logic 76 (4):1381-1402.
Michael Rathjen. The superjump in Martin-Löf type theory_. _Logic Colloquium '98, Proceedings of the annual European summer meeting of the Association for Symbolic Logic, held in Prague, Czech Republic, August 9–15, 1998, edited by Samuel R. Buss, Petr Hájek, and Pavel Pudlák, Lecture notes in logic, no. 13, Association for Symbolic Logic, Urbana, and A K Peters, Natick, Mass., 2000, pp. 363–386. [REVIEW]Michael Möllerfeld - 2002 - Bulletin of Symbolic Logic 8 (4):538-538.
Handbook of proof theory.Samuel R. Buss (ed.) - 1998 - New York: Elsevier.

Analytics

Added to PP
2010-08-30

Downloads
26 (#595,031)

6 months
9 (#290,637)

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