(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.