3
$\begingroup$

I am interested in combinatorial (worst-case) one-way functions. I came across this problem which may be related to coding theory problems (I am not an expert in coding theory).

INPUT: Two vectors $R_{n*1}$ and $C_{1*n}$.

QUESTION: Is there a binary matrix $A_{n*n}$ such that vector $R$ contains the parity check of each row in $A$ and vector $C$ contains the parity check of each column in $A$.

The parity check of a row (or column) is the sum of all bits Mod 2 (XOR operation).

What is the time complexity of this problem? Is it NP-complete? Is it efficiently solvable? Is this a known problem in coding theory?

Also, it is interesting to know the time-complexity of a variant in which vectors $R$ and $C$ contains the integer sum of the one's in each row and column in $A$.

EDIT: It is interesting to note that the Sum problem becomes $NP$-complete if the directed graph is required to be acyclic (see the link in Yuval's answer).

$\endgroup$
2
  • 2
    $\begingroup$ When you are given the actual sums, this is a known as the digraph realization problem. $\endgroup$ Aug 26, 2016 at 13:12
  • $\begingroup$ For the parity problem, you need the sum of row parities and column parities to be the same, and this probably suffices. $\endgroup$ Aug 26, 2016 at 13:15

1 Answer 1

5
$\begingroup$

Parity problem

It is clear that $\sum_i R_i \equiv \sum_j C_j \pmod{2}$ must hold if any solution exists. On the other hand, if this holds then some solution exists. Let $R$ contain $a$ ones, and let $C$ contain $b$ ones. We can assume without loss of generality that $a \geq b$. Arrange the rows and the columns so that $$ \begin{align*} &(R_1,C_1) = \cdots = (R_{n-a},C_{n-a}) = (0,0) \\ &(R_{n-a+1},C_{n-a+1}) = \cdots = (R_{n-b},C_{n-b}) = (1,0) \\ &(R_{n-b+1},C_{n-b+1}) = \cdots = (R_n,C_n) = (1,1) \end{align*} $$ Note that there is an even number of occurrences of the second type. We now construct a block diagonal matrix with the following blocks: $$ \begin{pmatrix} 0 \end{pmatrix} \times (n-a), \quad \begin{pmatrix} 1 & 0 \\ 1 & 0 \end{pmatrix} \times (a-b), \quad \begin{pmatrix} 1 \end{pmatrix} \times b $$

Sum problem

When the actual sums are given, we have the digraph realization problem, which can be solved efficiently.

$\endgroup$
1

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.