<p>When studying the complexity of checking identities in certain finite algebras, I came across the following decision problem:</p>
<blockquote>
<p><strong>Input:</strong> A positive integer <span class="math-container">$n \in N$</span> and a set of affine subspaces <span class="math-container">$H_1,H_2,\ldots,H_k$</span> of <span class="math-container">$\mathbb Z_2^n$</span> (where <span class="math-container">$\mathbb Z_2$</span> is the 2-element field).</p>
<p><strong>Question:</strong> For every <span class="math-container">$x \in \mathbb Z_2^n$</span>, let <span class="math-container">$n(x) = |\{H_i:x\in H_i \}|$</span>. Is <span class="math-container">$n(x)$</span> a multiple of 3 for all <span class="math-container">$x$</span>? Or, in other words, is every point of <span class="math-container">$\mathbb Z_2^n$</span> covered by <span class="math-container">$0$</span> modulo <span class="math-container">$3$</span> many of the affine subspaces?</p>
</blockquote>
<p>Note that there are no conditions on <span class="math-container">$n$</span>, <span class="math-container">$k$</span> and the dimension of the affine subspaces <span class="math-container">$H_i$</span>.</p>
<p>The problem is clearly in coNP, but unfortunately I am not able to prove anything more about its complexity. My hope is for it to be coNP-complete, since this would have nice implications for our research. But also if it was in P or equivalent to some coNP-intermediate problem this would be a really interesting fact to know.</p>
<p>Two observations:</p>
<ul>
<li>If we additionally assume that the codimension of all input subspaces <span class="math-container">$H_i$</span> is bounded by a constant (e.g. if every <span class="math-container">$H_i$</span> is a hyperplane) then the problem is in P. Thus any encoding of a coNP-complete problem would require using subspaces of arbitrary codimension.</li>
<li>I tried to encode the complement of some classical NP-complete problems, but did not succeed. In particular 'covering problems' like the Set cover problem seemed to be a natural choice. But that we count here 'modulo 3' seemed to be an obstacle in this approach.</li>
</ul>
<p>Thanks for every hint! :) In particular references to possibly related problems in the literature would be very welcome!</p>

CC BY-SA 4.0
2018-09-26T14:24:28.750Z
Note, this question is equivalent to determining that a given MOD3-AND-MOD2 circuit is a tautology (all assignments are satisfying ones). So e.g. the comment about codimension can be seen as each AND having constant fan-in; in that case each AND can be written as a short mod3 sum of MOD2s, and the circuit just becomes a multilinear polynomial over F3 (where satisfiabilty is very easy).
Ryan Williams
CC BY-SA 4.0
2018-10-01T08:16:42.627Z
@RyanWilliams: Thanks, this seems to be a helpful different point of view! Also there is plenty of literature on such circuits. I will update my post, if I find anything useful
user50712
<cc.complexity-theory><np-complete><algebra><algebraic-complexity><covering-problems>
Complexity of deciding whether subspaces of Z_2^n cover every point 3*x times
user50712
# Complexity of deciding whether subspaces of Z_2^n cover every point 3*x times

(Asked by: username_0 on 2018-09-25)

When studying the complexity of checking identities in certain finite algebras, I came across the following decision problem:

> **Input:** A positive integer $n \in N$ and a set of affine subspaces $H\_1,H\_2,\ldots,H\_k$ of $\mathbb Z\_2^n$ (where $\mathbb Z\_2$ is the 2-element field).
>
> **Question:** For every $x \in \mathbb Z\_2^n$, let $n(x) = |\{H\_i:x\in H\_i \}|$. Is $n(x)$ a multiple of 3 for all $x$? Or, in other words, is every point of $\mathbb Z\_2^n$ covered by $0$ modulo $3$ many of the affine subspaces?

Note that there are no conditions on $n$, $k$ and the dimension of the affine subspaces $H\_i$.

The problem is clearly in coNP, but unfortunately I am not able to prove anything more about its complexity. My hope is for it to be coNP-complete, since this would have nice implications for our research. But also if it was in P or equivalent to some coNP-intermediate problem this would be a really interesting fact to know.

Two observations:

* If we additionally assume that the codimension of all input subspaces $H\_i$ is bounded by a constant (e.g. if every $H\_i$ is a hyperplane) then the problem is in P. Thus any encoding of a coNP-complete problem would require using subspaces of arbitrary codimension.
* I tried to encode the complement of some classical NP-complete problems, but did not succeed. In particular 'covering problems' like the Set cover problem seemed to be a natural choice. But that we count here 'modulo 3' seemed to be an obstacle in this approach.

Thanks for every hint! :) In particular references to possibly related problems in the literature would be very welcome!

**Tags:** cc.complexity-theory, np-complete, algebra, algebraic-complexity, covering-problems

> **Comments:**
> **username_1**: Note, this question is equivalent to determining that a given MOD3-AND-MOD2 circuit is a tautology (all assignments are satisfying ones). So e.g. the comment about codimension can be seen as each AND having constant fan-in; in that case each AND can be written as a short mod3 sum of MOD2s, and the circuit just becomes a multilinear polynomial over F3 (where satisfiabilty is very easy).  
> **username_0**: @RyanWilliams: Thanks, this seems to be a helpful different point of view! Also there is plenty of literature on such circuits. I will update my post, if I find anything useful  

---

## 0 answers

