Is there any known decision version of matrix multiplication problem such that the time complexity of the best known algorithm for this decision problem is $O(n^k)$ for $n \times n$-dimensional matrices, where $k$ is bigger than 2 and preferable very close to $ \omega $ or the best known candidate of $\omega$ ($\omega$ is the optimal matrix-product constant)?

P.S. I am aware of matrix product verification problem (e.g. this post).

  • $\begingroup$ Crypto really isn't my field, but what about computing the $k$th bit of some cryptographic hash function of the matrix product (or a similar trick)? $\endgroup$ – Yonatan N Feb 19 '14 at 22:58

Let $H$ be some complex hash function (almost any function will do), mapping long bit strings down to a single bit. Then to decide whether $H( A \times B ) = 0$, you will basically need to multiply $A \times B$ and compute $H$ on the resulting product. Unless $H$ has very special properties, there won't be any short cut to this.

  • $\begingroup$ Do you think this problem is harder than matrix product verification problem (there is a link at the end of question)? $\endgroup$ – Abuzer Yakaryilmaz Feb 21 '14 at 14:32

While this doesn't answer your exact question, CFG parsing is a decision problem that was reduced from matrix multiplication (so it is as hard as matrix multiplication in a sense).

Specifically, in [1] it was shown that CFG parsing is as hard as boolean matrix multiplication. In particular, if CFG parsing (a decision problem) can be solved in $O(gn^{3-\epsilon})$ time, boolean matrix multiplication can be solved in $O(n^{3-\epsilon/3})$ time. An interesting aspect is that matrix multiplication can also be used for fast CFG algorithms, so the problems are computationally equivalent in a sense.

The reduction has some unusual aspects because boolean matrix multiplication requires $n^2$ output bits, whereas CFG parsing only requires one. To deal with this, the paper assumes that the CFG parser solves certain subproblems when parsing the string (and argues that this is a reasonable assumption to make). The reduction makes $n^2$ queries to these subproblems to obtain the product matrix.

Thus CFG parsing is a decision problem that is computationally as hard (in a sense) as matrix multiplication. However, this is not specifically a decision version of matrix multiplication, and furthermore, the reduction relies on the idea that CFG parsing is actually made up of $n^2$ decision subproblems.

  1. Lee, Lillian. "Learning of context-free languages: A survey of the literature." Techn. Rep. TR-12-96, Harvard University (1996).

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.