# complexity of a constraint satisfaction promise problem

(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 ​ promisecoQIPTIME$\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.

• 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. – Tayfun Pay Mar 15 '17 at 4:28
• How about YES = 1 in 3 SAT, NO = 2 in 3 SAT. ? :-) – Tayfun Pay Mar 15 '17 at 4:30
• "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. ​ ​ – user6973 Mar 15 '17 at 4:34
• 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? – Tayfun Pay Mar 15 '17 at 4:36
• All True part is not doable unless you have negations... And the same variable twice with opposite polarity within the same clause. – Tayfun Pay Mar 15 '17 at 4:41

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  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 , 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 .)

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:

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