For the following equivalent questions, you choose
whether-or-not the 3 variables in a clause must be distinct.

Is there an integer $k$ such that for all 3-SAT formulas $\mathcal{F}$ without negations,
if every ​ $(\leq k)$-clause sub-formula of $\mathcal{F}$ is 1-in-3 satisfiable then $\mathcal{F}$ is NAE-satisfiable?

Equivalently, is there an integer $k$ such that for all
3-SAT formulas $\mathcal{F}$ without negations, if $\mathcal{F}$ is not NAE-satisfiable then
$\mathcal{F}$ has a ​ $(\leq k)$-clause sub-formula which is not 1-in-3 satisfiable?

(The Fano plane shows that $k$ can't be less than $7$.)

Motivation: ​ ​ ​ That is the "low end" of my question
on cs.stackexchange which was inspired by the
possibility of generalizing Schaefer's dichotomy theorem
to constraint satisfaction promise problems.
Specifically, for the simplest non-trivial promise-constraint,
with m being the size of the input set, I have neither managed to
find evidence for it being in ​ promisecoQIP[2]TIME$\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 find evidence that it's not solvable
in coNTIME(O(1)) on essentially the most basic word RAM.
The former applies even when each variable occurs exactly twice
and "many m" gets replaced with "many even m" (since 3 is odd),
and the latter applies even when negative literals are allowed.

  • 10
    $\begingroup$ As D.W. wrote under the Computer Science question, could you please stop trying to fix the visual elements by putting HTML tags and LaTeX like < br > etc. which should be used only for semantic/logic reasons. It makes your posts look horrible on mobile devices. You should try reading your posts on a cellphone to get an idea of how bad they look. :) $\endgroup$
    – Kaveh
    Mar 3, 2016 at 1:35
  • $\begingroup$ @domotorp : ​ ​ ​ Not quite. ​ $S_k$ should instead be in $\binom{\mathcal{F}\hspace{.02 in}}k$, since it should be a sub-instance of $\mathcal{F}$. ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$
    – user6973
    Nov 20, 2016 at 7:14
  • $\begingroup$ @domotorp : ​ I believe my edit just simplified the statement. ​ ​ ​ ​ $\endgroup$
    – user6973
    Nov 20, 2016 at 7:26
  • 1
    $\begingroup$ @domotorp : ​ ​ ​ It has 7 lines, each with exactly 3 points. ​ Setting the points on any one line to true and the other points to false will 1-in-3-satisfy the 6 other lines, so all the (≤6)-clause sub-formulae of the corresponding 7-clause formula are 1-in-3-satisfiable. ​ However, that 7-clause formula is not even NAE-satisfiable. ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$
    – user6973
    Nov 20, 2016 at 9:12

1 Answer 1


So if I understood well, your problem in the language of graph theory would be as follows:

Is there a $k$ such that if for a $3$-uniform hypergraph for any $k$ of its edges we can select a $1$-shallow hitting set (a set of vertices that meets each of the $k$ edges in exactly one vertex), then the hypergraph is $2$-colorable?

The answer to this question is no because for any $g$ and $r$ there are $r$-uniform hypergraphs of girth $g$ with arbitrarily high chromatic number [Kostochka-Nesetril]. The girth $g$ of an $r$-uniform hypergraph is the smallest $g$ for which there are $g-1$ edges whose union has size at most $g(k-1)$. Thus, if a hypergraph has girth $g$, then any $g-1$ edges have a $1$-shallow hitting set by induction because their union looks like a tree. This means that locally it satisfies your 1-in-3 satisfiability condition, but it is not $2$-colorable, so there is no NAE-satisfying assignment for the whole hypergraph.

  • $\begingroup$ Where is it shown that "for any $g$ and $r$ ... chromatic number"? ​ (I see your reference's "exists by [9]" paragraph, but also do not see the result your reference cites [9] for in [9].) ​ ​ ​ ​ $\endgroup$
    – user6973
    Nov 20, 2016 at 15:04
  • $\begingroup$ @RickyDemer I think you want Corollary 13.4. I think the "$s$-circuitless" condition implies a lower bound on the girth (perhaps it's as simple as that $s$-circuitlessness implies the girth is at least $s+1$). The corollary follows easily from 13.3, whose proof is in yet another reference, but 13.3 is supposedly proved using the probabilistic method, so you might try to just prove what is needed from [9] from scratch. $\endgroup$ Nov 20, 2016 at 17:14
  • $\begingroup$ I don't see any "Corollary 13.4" in your reference. ​ (I also checked [9] in case you were referring to that, and didn't see it there either.) ​ ​ ​ ​ $\endgroup$
    – user6973
    Nov 20, 2016 at 17:23
  • 1
    $\begingroup$ It's more that I was looking at a different paper with almost the same name that was by Hajnal alone (link, for if you're curious). ​ Now looking at the paper you just linked to, their definition of "$s$-circuitless" is not obviously strong enough for my question - For 3-uniform hypergraphs, girth greater than 4 in your answer's sense automatically implies 2-colorability, since it forces every hyperedge to have a vertex that appears in no other hyper edge. ​ ​ ​ ​ $\endgroup$
    – user6973
    Nov 20, 2016 at 21:07
  • 1
    $\begingroup$ No hurry, the longer it stays unaccepted, the longer my name shall shine in the featured section of TCS.SE! $\endgroup$
    – domotorp
    Nov 21, 2016 at 14:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.