All reports by Author Alexander D. Scott:

__
TR04-111
| 30th November 2004
__

Piotr Berman, Marek Karpinski, Alexander D. Scott, Alexander D. Scott#### Computational Complexity of Some Restricted Instances of 3SAT

__
TR04-111
| 30th November 2004
__

Piotr Berman, Marek Karpinski, Alexander D. Scott, Alexander D. Scott#### Computational Complexity of Some Restricted Instances of 3SAT

__
TR03-049
| 25th June 2003
__

Piotr Berman, Marek Karpinski, Alexander D. Scott#### Approximation Hardness of Short Symmetric Instances of MAX-3SAT

__
TR03-022
| 11th April 2003
__

Piotr Berman, Marek Karpinski, Alexander D. Scott#### Approximation Hardness and Satisfiability of Bounded Occurrence Instances of SAT

Piotr Berman, Marek Karpinski, Alexander D. Scott, Alexander D. Scott

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

more >>>Piotr Berman, Marek Karpinski, Alexander D. Scott, Alexander D. Scott

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

more >>>Piotr Berman, Marek Karpinski, Alexander D. Scott

We prove approximation hardness of short symmetric instances

of MAX-3SAT in which each literal occurs exactly twice, and

each clause is exactly of size 3. We display also an explicit

approximation lower bound for that problem. The bound two on

the number ...
more >>>

Piotr Berman, Marek Karpinski, Alexander D. Scott

We study approximation hardness and satisfiability of bounded

occurrence uniform instances of SAT. Among other things, we prove

the inapproximability for SAT instances in which every clause has

exactly 3 literals and each variable occurs exactly 4 times,

and display an explicit ...
more >>>