# Is following SAT case in $\mathsf{P}$?

f(2, 3, 20) : 10011010
f(4, 20, 21) : 10101001
f(4, 20, 22) : 10010110
f(2, 4, 23) : 10011010
f(5, 23, 24) : 10101001
f(5, 21, 23) : 01101001
f(2, 5, 26) : 10011010
f(2, 3, 33) : 10101001
f(3, 22, 33) : 10000110
f(3, 21, 40) : 10100110
f(3, 21, 41) : 01101001
f(21, 41, 42) : 10101001
f(40, 42, 44) : 10010110
f(3, 4, 45) : 10101001
f(26, 45, 46) : 10101001
f(26, 45, 47) : 10010110
f(24, 46, 47) : 11001001
f(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}$?

• 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. – Yuval Filmus Jun 8 '17 at 21:51
• 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. – rus9384 Jun 8 '17 at 22:01

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.