7
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ 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). $\endgroup$ – Ryan Williams Sep 26 '18 at 14:24
  • $\begingroup$ @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 $\endgroup$ – user50712 Oct 1 '18 at 8:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.