Skip to main content
2 of 5
shortened lines to fit on mobile devices
user avatar
user avatar

Does every NO instance of this promise problem have a local refutation?

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

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 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} ,
{$\hspace{.02 in}$y,a,c},{B,a,z},{b,a,C} , {$\hspace{.02 in}$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) which was inspired by 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" gets replaced with "many _even_ m" (since 3 is odd),
and the latter applies even when [negative literals](https://en.wikipedia.org/wiki/Boolean_satisfiability_problem#Basic_definitions_and_terminology) are allowed.

user6973