New answers tagged constraint-satisfaction
1
You can't. There is no solver that can handle all constraints over the natural numbers and always finds a solution if one exists. The problem is undecidable, even without allowing variables in the exponent. (See, e.g., https://en.wikipedia.org/wiki/Hilbert%27s_tenth_problem.)
So, there is no one-size-fits-all solver.
For this reason, and for other reasons,...
1
Yes, it's possible. Let $S$ be the original linear problem, i.e., a conjunction of inequalities. You can form two LPs. One LP has the form $S \land x=0$, which can be solved with a LP solver. The other LP has the form $S \land 1 \le x \le 2$. If either one has a feasible solution, your problem has a feasible solution. This procedure takes polynomial ...
4
No. This problem is equivalent to XOR-3SAT, in which we interpret each clause as $x \oplus y \oplus z$, where $\oplus$ is the XOR operator, and ask whether it's possible to find values for all variables so that each clause is true. XOR-SAT can be solved in polynomial time using Gaussian elimination, with all arithmetic done modulo 2 (i.e., in the finite ...
2
By Schafer's Dichotomy Theorem, if a clause is expressible as a system of linear equations over Zmod2, it is in P. Thus it would not be NP-Complete.
Top 50 recent answers are included
