20
$\begingroup$

The following question arose as a side product of some work I have been part of recently. An $m$ by $n$ $(0,1)$-matrix $M$ is partial circulant if it can be formed by taking the first $m$ rows of a circulant matrix and all its entries are either $0$ or $1$. We assume that $m\leq n$.

Given such a partial circulant matrix $M$, what is the computational complexity of the following question?

Is there a non-zero vector $v\in \{-1,0,1\}^n$ such that $Mv=0$?

The problem is clearly in NP but my guess is that it is not NP-hard (unlike this related question). I have not, however, found a poly time solution.

Improve this question
$\endgroup$
2
  • $\begingroup$ would it be more natural to study the circulant case 1st vs the partial circulant? also (idea) the other problem answers are formulated in terms of subset sum problem, how would this problem be formulated that way (ie as a constrained or special case of subset sum problem)? note there are many subset sum variants studied in the literature that might be close... $\endgroup$
    – vzn
    Commented Jun 24, 2015 at 18:24
  • $\begingroup$ The circulant case was in fact considered at mathoverflow.net/questions/168474/… . However, it seems that there is fatal bug in one of the answers and the other answer is not a complete solution. $\endgroup$
    – Simd
    Commented Jun 24, 2015 at 18:40

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.