5

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
    As D.W. wrote under the [cs.se] 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. :) – Kaveh Mar 03 '16 at 01:35
  • @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}$. ​ ​ ​ ​ ​ ​ ​ ​ –  Nov 20 '16 at 07:14
  • @domotorp : ​ I believe my edit just simplified the statement. ​ ​ ​ ​ –  Nov 20 '16 at 07:26
  • 1
    @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. ​ ​ ​ ​ ​ ​ ​ ​ –  Nov 20 '16 at 09:12

1 Answers1

2

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.

domotorp
  • 13,931
  • 37
  • 93
  • 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].) ​ ​ ​ ​ –  Nov 20 '16 at 15:04
  • @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. – Andrew Morgan Nov 20 '16 at 17:14
  • 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.) ​ ​ ​ ​ –  Nov 20 '16 at 17:23
  • @Ricky So you believe me, but doubt that Kostochka and Nesetril cited correctly from Erdos-Hajnal? I think that 13.4 is here: http://www.renyi.mta.hu/~p_erdos/1966-07.pdf – domotorp Nov 20 '16 at 19:19
  • 1
    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. ​ ​ ​ ​ –  Nov 20 '16 at 21:07
  • @Ricky Indeed! I must admit that I've spent quite some time trying to figure out what they mean by girth, because in Kostochka-Nesetril there is no definition whatsoever for hypergraphs. – domotorp Nov 20 '16 at 21:14
  • @Ricky I've fixed the def, I think it should be correct now. – domotorp Nov 20 '16 at 21:30
  • Well, it took some time for me to work out the relevant version of "looks like a tree", and to see why circuitless graphs necessarily do so, but now this certainly seems to work. ​ I'll accept in about 24 hours if at that time I'm still not aware of any problem with your reasoning. ​ ​ ​ ​ –  Nov 21 '16 at 07:19
  • 1
    No hurry, the longer it stays unaccepted, the longer my name shall shine in the featured section of TCS.SE! – domotorp Nov 21 '16 at 14:16