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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.