Minimum propositional proof length is NP-hard to linearly approximate

Publisher： Cambridge University Press

E-ISSN： 1943-5886|66|1|171-191

ISSN： 0022-4812

Source： The Journal of Symbolic Logic, Vol.66, Iss.1, 2001-03, pp. : 171-191

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

Related content

The relative efficiency of propositional proof systems

By  

The Journal of Symbolic Logic, Vol. 44, Iss. 1, 1979-03 ,pp. : 36-50

Cambridge University Press

Access to resources Recommend Favorite

Minimum Manhattan Network is NP-Complete

By Chin Francis   Guo Zeyu   Sun He  

Discrete & Computational Geometry, Vol. 45, Iss. 4, 2011-06 ,pp. : 701-722

Springer Publishing Company

Access to resources Recommend Favorite

Combinatorics of first order structures and propositional proof systems

By Krajíček Jan  

Archive for Mathematical Logic, Vol. 43, Iss. 4, 2004-05 ,pp. : 427-441

Springer Publishing Company

Access to resources Recommend Favorite

Propositional proof systems, the consistency of first order theories and the complexity of computations

By  

The Journal of Symbolic Logic, Vol. 54, Iss. 3, 1989-09 ,pp. : 1063-1079

Cambridge University Press

Access to resources Recommend Favorite

On the minimum length of some linear codes

By Cheon E.   Maruta T.  

Designs, Codes and Cryptography, Vol. 43, Iss. 2-3, 2007-06 ,pp. : 123-135

Springer Publishing Company

Access to resources Recommend Favorite