ECCC - TR04-111

ECCC

Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login

Register

Classic Style

REPORTS > DETAIL:

Paper:

TR04-111 | 30th November 2004 00:00

Computational Complexity of Some Restricted Instances of 3SAT

Contact

Add Comment

TR04-111 Authors: Piotr Berman, Marek Karpinski, Alexander D. Scott, Alexander D. Scott
Publication: 30th November 2004 13:59
Downloads: 1578

Keywords:

3SAT, Bounded Occurrence Instances, Computational Complexity, NP-hardness, satisfiability, Witness Functions

Abstract:

We prove results on the computational complexity of instances of 3SAT in which every variable occurs 3 or 4 times.

ISSN 1433-8092 | Imprint