One More Occurrence of Variables Makes Satisfiability Jump from Trivial to NP-Complete
- 1 February 1993
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 22 (1) , 203-210
- https://doi.org/10.1137/0222015
Abstract
No abstract availableThis publication has 6 references indexed in Scilit:
- Approximation algorithms for combinatorial problemsPublished by Elsevier ,2007
- A parallel algorithmic version of the local lemmaRandom Structures & Algorithms, 1991
- An algorithmic approach to the Lovász local lemma. IRandom Structures & Algorithms, 1991
- On the r,s-SAT satisfiability problem and a conjecture of ToveyDiscrete Applied Mathematics, 1990
- A simplified NP-complete satisfiability problemDiscrete Applied Mathematics, 1984
- Asymptotic lower bounds for Ramsey functionsDiscrete Mathematics, 1977