7
$\begingroup$

Due to curiosity regarding possible extensions of Schaefer's dichotomy theorem, I wound up considering the "promise constraint" with 3 boolean inputs that's given by

$C(x,y,z) ​ ​ = \hspace{.1 in}\begin{cases} \hspace{.19 in}\text{ True} & \text{ if exactly one of } \hspace{.02 in}x,\hspace{-0.03 in}y,\hspace{-0.03 in}z\hspace{.02 in} \text{ is true} \\ \hspace{.19 in}\text{ False} & \text{ if } \hspace{.07 in}x=y=z \\ \text{promise fails} & \text{ otherwise.}\end{cases}$


What is the complexity of the following promise problem?

Input: ​ a 3-CNF formula with no negations
must output YES if: ​ the input has a 1-in-3 satisfying assignment
must output ​ NO if: ​ the input has no NAE satisfying assignment


In the following, define $m$ to be the number of promise-constraints in the 3-CNF formula provided as input.


I have neither managed to show that that problem is in promisecoQMATIME$\hspace{-0.02 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$, nor show that there does not exist a positive integer $k$ such that for every must-output-NO instance U of that problem, some $k$-constraint sub-instance of U is not 1-in-3 satisfiable.
(If there does exist such a k, then the promise problem is solvable in coNLOGTIME.)

$m = 10$ ​ is enough to refute ​ $k < 7$, ​ but I haven't yet found any refutation for ​$k = 7$. The rest of that sentence will apply even when each variable occurs exactly twice, if "infinitely many $m$" is replaced with "infinitely many even $m$" (since 3 is odd).

Motivation:
I was looking for non-trivial promise-constraints, to try to get an idea of whether or not Schaefer's theorem should extend to them. ​ To try to find one, I restricted attention to 3-variable boolean promise-constraints which only depend on how many of their inputs are true. ​ To be non-trivial, such constraints must be false when all of their inputs are equal, and must also have a way to be true. ​ Furthermore, to avoid being resolved by Schaefer, they must have non-trivial promise. The previous two sentences only leave 2 possibilities: the one I'm asking about, and the one which is instead true if and only if exactly two of the inputs are true. ​ However, the latter is equivalent to what I'm asking about, since it just reverses the roles of [$\hspace{.02 in}$True,False] values for the variables.

What I've Tried:
I do realize that it would be enough to be able to find a NAE-satisfying assignment when given a 1-in-3-satisfiable monotone 3-SAT formula, but my only idea for perhaps finding such assignments faster than brute force is looking for autarkies (bottom of page 15). (Additionally, I don't see any search-to-decision reduction for the promise problem, since the oracle could output YES to lead the solver to instances which fail the promise, and then output NO regardless of how the solver tries to simplify from there.) I have also tried to find a small gadget. ​ It is possible that some more complicated representation would help, but so I could run a search for such things, I only looked for 3-input-variable gadgets in which each each input variable is represented by only one output variable. My Python program's brute-force search for such gadgets with [at most 3 constraints] or [4 constraints and at most 3 non-input variables] did not find anything at all useful.

$\endgroup$
  • $\begingroup$ Still looks weird with sentences cut in half. Oh... Pure <br>, I see... $\endgroup$ – Evil Jan 16 '16 at 1:31
  • $\begingroup$ (The example I have for why k can't be less than 7 is [(0,1,2),(0,3,4),(0,3,5),(0,6,7),(1,3,6),(1,4,7),(1,5,8),(2,3,7),(2,4,8),(2,5,6)]. ​ I found that with random search followed by canonicalization, so I don't have any combinatorial or geometric description of it, and I correspondingly don't have any non-brute-force proof of it having no NAE satisfying assignment or of its 6-constraint sub-instances all having 1-in-3 satisfying assignments.) ​ ​ ​ ​ $\endgroup$ – user12859 Jan 16 '16 at 5:38
  • 3
    $\begingroup$ Please don't insert manual line breaks (<br>) in the middle of lines, to try to control where lines break. Not everyone has the same size screen you do, and this will look horrible on some screen widths. Thank you for your understanding. $\endgroup$ – D.W. Jan 16 '16 at 5:47

Your Answer

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