Generalized CNF satisfiability problems and non-efficient approximability
- 17 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
No abstract availableKeywords
This publication has 22 references indexed in Scilit:
- The correlation between the complexities of the non-hierarchical and hierarchical versions of graph problemsPublished by Springer Nature ,2006
- NP-complete problems have a version that's hard to approximatePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Paths and cycles in finite periodic graphsPublished by Springer Nature ,1993
- Polynomially bounded minimization problems which are hard to approximatePublished by Springer Nature ,1993
- Maximum bounded 3-dimensional matching is MAX SNP-completeInformation Processing Letters, 1991
- The Complexity of Very Simple Boolean Formulas with ApplicationsSIAM Journal on Computing, 1990
- Nonlinear Algebra and Optimization on Rings are “Hard”SIAM Journal on Computing, 1987
- On the Computational Complexity of Algebra on LatticesSIAM Journal on Computing, 1987
- Planar Formulae and Their UsesSIAM Journal on Computing, 1982
- Reducibility among Combinatorial ProblemsPublished by Springer Nature ,1972