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

more >>>

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

more >>>

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 >>>

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 >>>