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

replaced http://cs.stackexchange.com/ with https://cs.stackexchange.com/

Source Link

edited Apr 13, 2017 at 12:48

1

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](httphttps://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[QIP\[2\]](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:Q#qip2)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.

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](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[QIP\[2\]](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:Q#qip2)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.

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](https://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[QIP\[2\]](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:Q#qip2)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.

Notice removed Draw attention by user6973

occurred Nov 22, 2016 at 17:17

Bounty Ended with domotorp's answer chosen by CommunityBot

occurred Nov 22, 2016 at 17:17

simplified statement

Source Link

edited Nov 20, 2016 at 7:26

user6973

For the following equivalent questions, replace _ with your choice of either "sets" or "multisets"you choose
whether-or-not the 3 variables in a clause must be distinct.

Is there a positivean integer $k$ such that for all finite sets of3-SAT formulas $\mathcal{F}$ without negations,
at least $k$ [[$\hspace{.03 in}$_ of variables] with cardinality 3], ifif every $k$$(\leq k)$-element
subsetclause sub-formula of $\mathcal{F}$ is 1-in-3 satisfiable then the set$\mathcal{F}$ is NAE-satisfiable?

Equivalently, is there a positivean integer $k$ such that for all
for all finite sets of at least3-SAT formulas $k$ [[$\hspace{.03 in}$_ of variables] with cardinality 3]$\mathcal{F}$ without negations,
if that set if $\mathcal{F}$ is not NAE-satisfiable then it has a
$k$$\mathcal{F}$ has a $(\leq k)$-element subsetclause 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](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[QIP\[2\]](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:Q#qip2)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.

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?

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

**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[QIP\[2\]](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:Q#qip2)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.

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](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[QIP\[2\]](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:Q#qip2)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.

Notice added Draw attention by user6973

occurred Nov 18, 2016 at 23:24

Bounty Started worth 300 reputation by CommunityBot

occurred Nov 18, 2016 at 23:24

gave simpler example

Source Link

edited Sep 19, 2016 at 19:47

user6973

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}(The }
showsFano plane 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$7$.)

**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]co[QIP\[2\]](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:Q#qmaQ#qip2)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.

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.

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?

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

**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[QIP\[2\]](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:Q#qip2)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.

Notice removed Draw attention by CommunityBot

occurred Mar 12, 2016 at 23:13

Bounty Ended with no winning answer by CommunityBot

occurred Mar 12, 2016 at 23:13

Notice added Draw attention by user6973

occurred Mar 4, 2016 at 21:14

Bounty Started worth 150 reputation by CommunityBot

occurred Mar 4, 2016 at 21:14

shortened lines to fit on mobile devices

Source Link

edited Mar 4, 2016 at 21:14

user6973

Loading

Tweeted twitter.com/StackCSTheory/status/705522563049529345

occurred Mar 3, 2016 at 22:37

Source Link

asked Mar 2, 2016 at 15:54

user6973

Loading

Stack Exchange Network

Return to Question