8
$\begingroup$

(This is the "upper end" of my question from over 10 months ago on cs.stackexchange.
That question and the "lower end" I asked here over 8 months ago,
which I also have a bounty on, are both unanswered.
These are screenshots of what this post should look like, in case it's not rendering correctly.)


beginning of Motivation Section:

I started wondering whether-or-not Schaefer's dichotomy theorem
can be extended to promise-constraints ​ As part of that, I looked for
the simplest promise-constraint for which the answer is not trivial:

To avoid Schaefer's theorem already applying, there must be at least one input tuple for which the promise fails. ​ For the same reason as that theorem, all-true and all-false must give NO, and there must be more than one input that gives YES. ​ In particular, there must be more than four possible inputs, so the promise-constraint must be over at least 3 variables. ​ To get a simple one, suppose it is over exactly 3 variables and is symmetric, i.e., depends only on how many of its inputs are true, not which ones those are. ​ In that case, either 2-true gives YES and the promise fails for 1-true, of 1-true gives YES and the promise fails for 2-true. ​ By just flipping each variable, those are equivalently hard, so to provide a shorter formal statement and "nicer" name, I will use the latter, i.e., exactly-1-true gives YES and the promise fails for 2-true.

end of motivation section

My Question


Let “positive 1.2-in-3-SAT" be the promise problem

Inputs have the syntax of 3-SAT without negations
must output YES if: ​ ​ ​ the input is 1-in-3-satisfiable
must output ​ NO if: ​ ​ ​ the input is not NAE-satisfiable

.


What is that problem's complexity?

You get to choose whether-or-not a variable can occur twice in a single promise-constraint.


(A variable occurring 3 times in a single promise-constraint
would automatically make it a must-output-NO instance.)

Obviously, the identity function is a reduction from the promise problem to positive 1-in-3-SAT
and to positive NAE-SAT, so GC(O(m),coNLOGTIME) can solve the promise problem.
However, there is a seemingly-trivial observation which leads to a
combinatorial obstruction to "simple" NP-hardness proofs for positive 1.2-in-3-SAT:


For any set of variables that meets at least one promise-constraint more than once,
there is no 1-in-3-satisfying assignment in which those variables are all true.
Conversely, for any set of variables that meets each promise-constraint at most once, for any
1-in-3-satisfying assignment, possibly-modifying it to make all of the variables in that set true gives a NAE-satisfying assignment. ​ In particular, the disjunction of two 1-in-3-satisfying assignments
is always a NAE-satisfying assignment. ​ To elaborate on the consequences of that,
assume positive 1.2-in-3-SAT has a gadget that implements a promise-constraint C, such that
the gadget "represents and interprets C's variables in the same way as each other", i.e.,

(correspondence:) ​ each of C's input variables corresponds
to an ordered subset of the variables in the gadget
and
(similar way:) ​ those subsets are of the same size as each other; I'll call that size j
and
(represents:) ​ there is a function ​ $forward$ ​ from the domain of C's variables
to {False,True}$\hspace{.02 in}$j such that for each YES input to C, there is a 1-in-3-satisfying
assignment to the gadget such that for each of C's input variables x,
[the assignment to the gadget-variables x corresponds to in their order] is $forward$(x)
and
(interprets:) ​ there is a function ​ $backward$ ​ from {False,True}$\hspace{.02 in}$j to the domain to C's variables such that for each NAE-satisfying assignment to the gadget, [setting each of C's input variables x to
[$backward$ ​ of [x's corresponding gadget-variables in their order]]] does not cause C to give NO

. ​ ​ ​ In that case, for each of C's variables x and y, if C has a YES input such that (x,y)=(a,b) and
a YES input such that (x,y)=(b,a), then it has an input such that x=y but it does not give NO.
In particular, such gadgets cannot even implement promise-coloring.


Also, the complement of a 1-in-3-satisfying assignment is always a NAE-satisfying assignment, which imposes weaker restrictions on the kinds of gadgets that positive 1.2-in-3-SAT might have.


Is anything else known about the possibility of positive 1.2-in-3-SAT being
"CSP-complete" like 3-SAT and positive 1-in-3-SAT and positive NAE-SAT,
i.e., having gadgets for every possible constraint?

In particular, with $m$ being the number of promise-constraints, showing that the promise problem is in ​ promisecoQIP[2]TIME$\hspace{-0.03 in}\big(\hspace{-0.04 in}$2o(m)$\hspace{-0.03 in}\big)\hspace{-0.04 in}\big/\hspace{-0.04 in}$q2o(m) ​ for infinitely many $m$ would more-than suffice.

$\endgroup$
  • $\begingroup$ Let's say that we are given a Boolean expression F in 3-CNF, where none of the literals are negated. Ok... We are promised that there is always a solution, since you want it to be YES = 1-in-3-SAT and NO = NAE-SAT. However, what you are missing is that F could be both 1-in-3-SAT and NAE-SAT at the same time. For example, it can have a satisfying truth assignment, where exactly 1 literal is satisfied so it is 1-in-3-SAT, but this also puts it in NAE-SAT since the literals of all of the clauses are not all True or False. $\endgroup$ – Tayfun Pay Mar 15 '17 at 4:28
  • $\begingroup$ How about YES = 1 in 3 SAT, NO = 2 in 3 SAT. ? :-) $\endgroup$ – Tayfun Pay Mar 15 '17 at 4:30
  • $\begingroup$ "this also puts it in NAE-SAT", meaning it's not not NAE-satisfiable, so I don't see the problem with what I wrote. ​ ​ $\endgroup$ – user6973 Mar 15 '17 at 4:34
  • $\begingroup$ Yes. I just saw that you want ~NAE-SAT... So you want all of the literals of each clause to be either all True or all False. Correct? $\endgroup$ – Tayfun Pay Mar 15 '17 at 4:36
  • $\begingroup$ All True part is not doable unless you have negations... And the same variable twice with opposite polarity within the same clause. $\endgroup$ – Tayfun Pay Mar 15 '17 at 4:41
2
$\begingroup$

Concerning the question whether Shaefer’s dichotomy theorem (or more generally, the Feder–Vardi conjecture, recently proved by Bulatov and Zhuk) can be generalized to promise problems: the complexity of promise CSPs is currently a hot research topic. It is still very much open if there is such a dichotomy even for Boolean PCSPs. However, partial results are known, in particular Brakensiek and Guruswami [1] prove dichotomy for symmetric Boolean PCSPs that allow for negation of variables.

In particular, the “1.2-in-3-SAT” problem is solvable in polynomial time—even if we allow negative literals—by Theorem 2.6 in [1], as it has the alternating threshold functions $x_1-x_2+x_3-\dots-x_{L-1}+x_L$ as weak polymorphisms. The paper gives in fact two different algorithms.

Algorithm 1:

Let $C$ be the input $3$-CNF. Identifying negative literals $\overline{x_i}$ with $1-x_i$, let $L_C$ be the linear system consisting of the equations $$u+v+w=1$$ for each clause $\{u,v,w\}\in C$. Using e.g. a polynomial-time algorithm for Hermite normal forms, compute an integer solution $(x_1,\dots,x_n)$ of $L_C$ if it exists.

If there is no solution, then $C$ is not 1-in-3 satisfiable.

If there is a solution, then $$x'_i=\begin{cases}1&x_i\ge1,\\0&x_i\le0\end{cases}$$ defines a NAE-satisfying assignment of $C$.

(Both claims are straightforward to verify.)

Algorithm 2:

Let $P_C$ be the linear program consisting of the linear system $L_C$ above and the bounds $$0\le x_i\le1$$ for all variables $x_i$.

If for some $i$, neither $P_C\cup\{x_i=0\}$ nor $P_C\cup\{x_i=1\}$ is feasible, then $C$ is not 1-in-3-satisfiable. (This is obvious.)

Otherwise, $C$ is NAE-satisfiable. (This requires some work to prove, see §3.2 in [1].)

The corresponding promise search problem is solvable in polynomial time as well: given a 1-in-3-satisfiable $3$-CNF $C$, compute a NAE-satisfying assignment to $C$. Algorithm 1 does just that; the paper mentions that Algorithm 2 can also be extended to yield this.

Reference:

[1] Joshua Brakensiek and Venkatesan Guruswami, Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy, arXiv:1704.01937 [cs.CC].

$\endgroup$

Your Answer

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