The \(k\)-SATISFIABILITY problem remains NP-complete for dense families

DOI10.1016/0012-365X(94)90175-9zbMath0803.68052MaRDI QIDQ1322290

Ingo Schiermeyer

Publication date: 2 January 1995

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

NP-complete\(k\)-SATISFIABILITY problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• A simplified NP-complete satisfiability problem
• One More Occurrence of Variables Makes Satisfiability Jump from Trivial to NP-Complete
• Two-Processor Scheduling with Start-Times and Deadlines