When multiplying integer numbers $A$ and $B$, one can use a 0-1 matrix to represent one of the multiplication steps. For example, given numbers (written in binary) $A=1101$ and $B=1011$ the matrix is: $$\begin{matrix} 1&0&1&1\\ 0&0&0&0\\ 1&0&1&1\\ 1&0&1&1 \end{matrix}$$

The top row of the matrix corresponds to the least significant bit of $A$, the bottom row corresponds to $A$'s most significant bit. The leftmost column and the rightmost column correspond to the most significant bit and the least significant bit of $B$ respectively.

The next step for multiplication is to count the sum of bits in each diagonal. Let's denote this array as $D$. In this case (we start from the most significant term), it's $D=1,1,1,3,1,1,1$.

The final step is to apply carry operation to $D$ until every element is $0$ or $1$. In this example it becomes $1,0,0,0,1,1,1,1$, i.e. the number is $143$ (in decimal).

Now, consider the following variant of factoring:

Given a number $N$ decide if there exists a factoring of depth at most $d$.

Where depth is defined as $\max(D)$ and $d$ is the parameter. For example, in case $d=2$, the answer would be negative for the above number (since it's a semiprime there is only one way to write the matrix (not counting $AB=BA$), and that matrix has a diagonal with $3>2$ positive bits).

Aside from that it's in $\mathsf P$ for $d=1$ (via polynomial factoring), can anything be said about the complexity of this problem?

  • $\begingroup$ The $BA$ matrix would be $\begin{matrix}1&1&0&1\\\\1&1&0&1\\\\0&0&0&0\\\\1&1&0&1\end{matrix}$ which (as it should) creates the same array $D$. Basically, the matrix has an anti-diagonal symmetry (in respect to counting $D$). $\endgroup$
    – rus9384
    Commented Jan 15 at 13:38


Your Answer

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