0
$\begingroup$
f[1](2, 3, 20) : 10011010
f[2](4, 20, 21) : 10101001
f[3](4, 20, 22) : 10010110
f[4](2, 4, 23) : 10011010
f[5](5, 23, 24) : 10101001
f[6](5, 21, 23) : 01101001
f[7](2, 5, 26) : 10011010
f[8](2, 3, 33) : 10101001
f[9](3, 22, 33) : 10000110
f[10](3, 21, 40) : 10100110
f[11](3, 21, 41) : 01101001
f[12](21, 41, 42) : 10101001
f[13](40, 42, 44) : 10010110
f[14](3, 4, 45) : 10101001
f[15](26, 45, 46) : 10101001
f[16](26, 45, 47) : 10010110
f[17](24, 46, 47) : 11001001
f[18](24, 44, 47) : 01101001

Each f[i](a, b, c) : truth-table means some boolean formula of 3 variables $x_a, x_b, x_c$. The main formula is conjunction of them all (I just converted CNF for 53 factorization circuit to such form and managed to reduce it to given instance).

$$\Phi = f_1 \land f_2 \land\ ...\ \land f_n$$

What I think is that now I need only logarithmic (or even constant) amount of all possible assignments to see if it's satisfiable.

For example, I can take $x_2 = 1$ and it'll automatically result in $x_{20} = 0, x_{21} = 0, x_4 \neq x_{22}, x_{23} = 0,$ etc. It seems that half of all variables will automatically be assigned, if I'll just put one.

So, is it in $\mathsf{P}$?

$\endgroup$
  • 2
    $\begingroup$ The class $\mathsf{P}$ is a property of problems or languages, not of instances. Every instance can be solved correctly in $O(1)$ by some algorithm. $\endgroup$ – Yuval Filmus Jun 8 '17 at 21:51
  • $\begingroup$ I mean that generally every subformula would have at most half positive assignments. So, it seems that I reduce it to 2-SAT (2 formulas). They are prior and then I can proceed with other subformulas. $\endgroup$ – rus9384 Jun 8 '17 at 22:01
1
$\begingroup$

This answer assumes the following interpretation of your question:

What is the complexity of the following problem? Decide whether a given CSP is satisfiable, where at most half of the assignments satisfy each constraint.

It is likely that this problem is either in $\mathsf{P}$ or $\mathsf{NP}$-complete. In fact, if we bound the width of the constraints (how many variables appear in them), then Schaefer's dichotomy theorem implies that the problem is either in $\mathsf{P}$ or $\mathsf{NP}$-complete, giving a criterion to decide which of these possibilities holds.

In your case, it seems likely that the problem is $\mathsf{NP}$-complete already for width 3. You can verify (or refute) this using the criterion in Schaefer's theorem, which can be found in the Wikipedia article linked to above.

$\endgroup$
  • $\begingroup$ What is really interesting is that my algorithm really divides it to disjunction of two 2-CNF. All factorization circuits look like that. However, general SAT is a bit harder. $\endgroup$ – rus9384 Jun 8 '17 at 22:45

Your Answer

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

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