0
$\begingroup$

This variant of #Positive 2-SAT is defined as follows :

We are given a set of variables :

(a,b,c,d,e)

we can form our 2-literal clauses from these set of variables but we want the input in this variant such that for example if we are given a clause (a,e) then this input must contain every possible 2-literal clause from variables below variable ( e ) and every such combination must contain variable ( e ), Thus if we given (a,e) then the input must also contain (b,e) ,(c,e) ,(d,e) as well ,and if the input contain (a,c),(b,d) these clauses then the input must also contain (b,c) ,(a,d) ,(c,d).

Is this variant of #Positive-2SAT ,where we have this kind of restriction on the input ,still #P-complete?

I have no idea as to how to show its complexity and haven't been able to find any sort of text on this type of variant.

My motivation for this is know more about the how much restrictions we can put on the input without changing the complexity status of the problem.

$\endgroup$
1
  • $\begingroup$ What have you tried? What have you come up with so far? What is the motivation for asking this? Can you say more about one might care about the answer? $\endgroup$
    – D.W.
    Feb 26, 2023 at 7:15

1 Answer 1

2
$\begingroup$

It can be solved in polynomial time, and thus is unlikely to be #P-complete. Every such formula has the form

$$\varphi = \bigwedge_{j=1}^{k} \bigwedge_{i=1}^{a_j-1} (x_i \lor x_{a_j})$$

where $a_1,\dots,a_k$ is some sequence of variable indices and the variables are $x_1,\dots,x_n$. Let's assume (without loss of generality) that $a_1 < \cdots < a_k$.

Then every satisfying assignment to $\varphi$ has the form

$$\begin{align*}&x_1=x_2=\cdots=x_{a_t-1}=\text{True},\\ &x_{a_t}=\text{False},\\ &x_{a_{t+1}}=x_{a_{t+2}}=\cdots=x_{a_k}=\text{True} \end{align*}$$

for some $t$. The number of satisfying assignments of this form is $2^{n_t}$ where

$$n_t=|\{a_t+1,a_t+2,\dots,n\} \setminus \{a_{t+1},a_{t+2},\dots,a_k\}|$$

which can be readily computed. Thus, the total number of satisfying assignments to $\varphi$ is

$$2^{n_1} + 2^{n_2} + \dots + 2^{n_k},$$

which can be computed in polynomial time.

$\endgroup$
1
  • $\begingroup$ Thank you for answering. $\endgroup$
    – Anuj
    Feb 27, 2023 at 10:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.