In this post ,I introduced a new variant of #Positive-2-SAT .
This version of problem puts restrictions on the inputs of the #Positive-2-SAT such that we can only choose at max only 2 clauses from each set mentioned below to form our set of input clauses:
- A = [ ab ,ac ,ad ,ae ]
- B = [ bc ,bd ,be ]
- C = [ cd ,ce ]
- D = [ de ]
A valid input to this variant of #Positive 2-SAT would be (ab ,ac ,bc ,cd) here we have only at max 2 clauses form each set mentioned above.
An invalid input to this variant of #Positive 2-SAT would be (ac ,ad ,ae ,bc ,cd) this is invalid as we have chosen more than 2 clauses from set A, mentioned above, thus its not a valid input to this version of the problem as we must only choose at max 2 clause form each set.
The complexity status of this problem is still not known ,but we do know ,from this post ,that if we allow to choose at max only 3 clause from each set mentioned above ,then this problem is #P-complete.
I want to ask if this is #P-complete if we must select at least (K_i -3) clasues from each set of clauses mentioned above to form our set of input clauses for this new variant of #Positive-2-SAT ,we can select more than (k_i-3) clauses from each ,but its compulsary to select at least (k_i - 3) clauses from each set [ A ,B ,C ,D ,....].
Here ,k_i is the lenght of each set :
k_A is length of set A k_B is the length of set B and so on.
Each set has different length because of how they are defined in my post.
My motivation for this problem is due to the fact that this problem is like opposite to the problem where we allowed to select only at max 3 clauses from each set [ A ,B ,C ,D ,....] ,and we know that, that problem is #P-complete ,thus I was wondering if its "opposite" , where we must select at least (K_i -3) clauses from each set [A, B ,C ,D ,...] is also #P-complete or not?