Uniquely Satisfiable -Regular (,)-SAT Instances.

Unique -SAT is the promised version of -SAT where the given formula has 0 or 1 solution and is proved to be as difficult as the general -SAT. For any k ≥ 3 , s ≥ f ( k , d ) and ( s + d ) / 2 > k - 1 , a parsimonious reduction from -CNF to -regular (,)-CNF is given. Here regular (,)-CNF is a subclass of CNF, where each clause of the formula has exactly distinct variables, and each variable occurs in exactly clauses. A -regular (,)-CNF formula is a regular (,)-CNF formula, in which the absolute value of the difference between positive and negative occurrences of every variable is at most a nonnegative integer . We prove that for all k ≥ 3 , f ( k , d ) ≤ u ( k , d ) + 1 and f ( k , d + 1 ) ≤ u ( k , d ) . The critical function f ( k , d ) is the maximal value of , such that every -regular (,)-CNF formula is satisfiable. In this study, u ( k , d ) denotes the minimal value of such that there exists a uniquely satisfiable -regular (,)-CNF formula. We further show that for s ≥ f ( k , d ) + 1 and ( s + d ) / 2 > k - 1 , there exists a uniquely satisfiable -regular ( k , s + 1 ) -CNF formula. Moreover, for k ≥ 7 , we have that u ( k , d ) ≤ f ( k , d ) + 1 .