0
$\begingroup$

Exactly 1 in 3SAT (X3SAT) is known to be NP-Complete. It remains NP-Complete even if we only consider instances that are monotone and linear. Monotone means all of the literals are positive. Linear means no two clauses share more than one variable in common. If $n$ is the number of variables then the maximum number of clauses for $n$ is $O(n^2)$.

Let $m$ be the number of clauses in a linear, monotone X3SAT instance. There is only one instance each for $m=1, 2$. There are $2$ instances with $3$ clauses and $4$ instances with $4$ clauses.

(a,b,c)(c,d,e)(e,f,g)(d,h,i) - 3-chain with branch

(a,b,c)(c,d,e)(a,d,f)(f,g,h) - 3-loop with branch

(a,b,c)(c,d,e)(e,f,g)(g,h,i) - 4-chain

(a,b,c)(c,d,e)(e,f,g)(a,g,h) - 4-loop

Has there been any research into the maximum number of distinct monotone, linear X3SAT instances with $m$ clauses? By distinct I mean the ordering of the variables is ignored. Also assume the instance is connected.


Some corrections. There are 3 instances with 3 clauses and 6 instances with 4 clauses.

(a,b,c)(c,d,e)(e,f,g) - 3-chain

(a,b,c)(c,d,e)(a,d,f) - 3-loop

(a,b,c)(a,d,e)(a,f,g) - 3-star

(a,b,c)(c,d,e)(e,f,g)(g,h,i) - 4-chain

(a,b,c)(c,d,e)(e,f,g)(a,g,h) - 4-loop

(a,b,c)(a,d,e)(a,f,g)(a,h,i) - 4-star

(a,b,c)(c,d,e)(e,f,g)(d,h,i) - 3-chain with length 1 branch

(a,b,c)(c,d,e)(a,d,f)(f,g,h) - 3-loop with length 1 branch

(a,b,c)(a,d,e)(a,f,g)(g,h,i) - 3-star with length 1 branch

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.