Skip to main content
1 of 5
user avatar
user avatar

Do NO instances of this promise problem always have local refutations?

For the following equivalent questions, replace _ with your choice of either "sets" or "multisets".

Is there a positive integer $k$ such that for all sets of at least $k$ [[$\hspace{.03 in}$_ of variables] with cardinality 3],
if every $k$-element subset is 1-in-3 satisfiable then the set is NAE-satisfiable?

Equivalently, is there a positive integer $k$ such that for all finite sets of
at least $k$ [[$\hspace{.03 in}$_ of variables] with cardinality 3], if that set is not NAE-satisfiable
then it has a $k$-element subset which is not 1-in-3 satisfiable?

{ {a,x,A} , {c,x,C} , {x,b,y},{x,B,y} , {y,a,c},{B,a,z},{b,a,C} , {y,A,C},{b,A,z},{B,A,c} }
shows that $k$ can't be less than $7\hspace{-0.04 in}$, although I found that and its indicated symmetry
by random search followed by brute force; I don't "understand"
why it works or even have any non-brute-force proof that it works.


**Motivation:** ​ ​ ​ That is the "low end" of my question [on cs.stackexchange](http://cs.stackexchange.com/q/51828/12859) about the possibility
of generalizing [Schaefer's dichotomy theorem](https://en.wikipedia.org/wiki/Schaefer%27s_dichotomy_theorem) to constraint satisfaction [promise](https://en.wikipedia.org/wiki/Promise_problem) 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
[promise](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:P#promisebqp)co[QMA](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:Q#qma)T[IME](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N#ntime)$\hspace{-0.02 in}\big(\hspace{-0.04 in}$2[o](https://en.wikipedia.org/wiki/Big_O_notation#Little-o_notation)(m)$\hspace{-0.03 in}\big)\hspace{-0.04 in}\big/\hspace{-0.04 in}$[q](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:Q#qmaqpoly)2[o](https://en.wikipedia.org/wiki/Big_O_notation#Little-o_notation)(m) ​ for infinitely many m, nor find evidence that
it's not solvable in [co](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:C#conp)N[TIME](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N#ntime)(O(1)) on essentially the most basic [word RAM](https://duckduckgo.com/?q=%22word+RAM%22+complexity).
The former applies even when each variable occurs exactly twice and "many m" is replaced
with "many _even_ m" (since 3 is odd), and the latter applies even if [negative literals](https://en.wikipedia.org/wiki/Boolean_satisfiability_problem#Basic_definitions_and_terminology) are allowed.

user6973