8

While browsing old CStheory.se posts, I ran across a fascinating blog post on the matrix mortality problem. Unless I've misinterpreted the problem, it states that given a finite collection of 3 x 3 matrices with integer entries for each matrix value, one must decide if there exists a finite product of those matrices that equals a matrix comprised of all zeros.

Amazingly, this problem is undecidable, due to a reduction from the Post correspondence problem. My question is: Given the undecidability of the problem, and its link to a problem that is linked to Turing machines, can you show that there exists a way to characterize (for example) all r.e. languages, the class P, and the class NP using matrices?

I've done a little work on this myself, but lack the training to be sure if my belief is correct. This problem would, I think, require a little bit of work on the reader's part to solve.

I don't know how to use LaTeX to write matrices on SE, but here's my first attempt to characterize NP:

Given a finite set $S$ of 3 x 3 matrices with integer entries and an integer $k$ as an NP "query," let an additional matrix $M$ be taken as a "structure." The "query" accepts the "structure" if there exists a product of $|M|^k + k$ matrices from $S$ that equals a matrix that consists of only zeros.

This attempt is not complete and does include any proof, as you see, but I wanted to give my first thoughts on the problem to see if a more sophisticated attempt could be made to formalize a notion of matrix complexity. This is interesting because, like Fagin's characterization of NP using descriptive complexity, it could be used to characterize NP in a machine-independent fashion.

Community
  • 1
  • Does the usage of the terminology, "matrix descriptive complexity", here have anything to do with descriptive complexity? It seems to me that you are attempting to express complexity classes using matrix operations rather than applying finite model theory. If so, you may want to remove the descriptive complexity tag. It might also be useful for us if you clarified the distinction or connection between your idea and Descriptive Complexity. – mdxn Sep 30 '13 at 18:03
  • I'm not an expert, but I had believed that "descriptive" complexity is named as it is because it is independent of Turing machines. "Descriptive" doesn't mean "logical" or "using finite model theory"--I don't think. I added the descriptive complexity tag because the generation of alternate, machine-independent characterizations of complexity classes is the goal of descriptive complexity. –  Sep 30 '13 at 19:03
  • Although the ordinary English word "descriptive" doesn't mean "using logic/finite model theory", the technical term "descriptive complexity" does mean that. – David Richerby Sep 30 '13 at 20:23
  • Ok. I'll change the question. –  Sep 30 '13 at 20:28
  • 1
    It could be interesting to investigate the efficiency of a "mortality-problem machine",i.e. a machine that given a set of 3x3 matrices $M_1,...,M_n$ finds a sequence of indices $i_k$ such that $M_{i_1} \cdot ... \cdot M_{i_m} = 0$. The number of multiplications $m$ can be seen as the "time" required to perform the computation. Can it simulate an arbitrary Turing machine $T$ on input $x$ with only a polynomial time slowdown? ($m = O(f(|x|)^k)$, for some $k$, where $f(|x|)$ is the running time of $T$ on $x$. – Marzio De Biasi Sep 30 '13 at 21:49
  • @MarzioDeBiasi , this is what I am getting at. Because matrix mortality reduces from the Post correspondence problem, and the Post problem can simulate Turing machines, I suspect that there is a way to simulate Turing machines on an input with matrices, and perhaps even capture complexity classes. This was the motivation for the question. My concern is that I am unsure of how to specify an input to such a "mortality-problem machine." –  Oct 01 '13 at 00:59
  • phil your idea is a little too sketchy in its current form but was thinking something close along the lines of @marzio 's comment. am aware of at least 2 other problems that seem to have a similar property of ranging from Turing Complete through all the different complexity classes based on adjusting/limiting a parameter somewhat similar to this problem, but this concept is not widely known (imho undeservedly so, it seems significant & worth closer attn). more details, further chat? – vzn Oct 01 '13 at 15:13

1 Answers1

1

This isn't a characterization of NP: it's just an NP-complete problem (well, I assume it's NP-complete, anyway). OK, if so, you could characterize NP as the class of problems reducible to your matrix problem but how are you going to define reductions? Using reductions from some existing model of computation (e.g., Turing machines) would be self-defeating. What advantages would such a characterization have over, say, considering NP to be the class of problems reducible to, say, independent set?

Also, the "structure" matrix $M$ plays no role in the problem except via its determinant so there's no reason for it to be a matrix, rather than just a natural number.

David Richerby
  • 2,765
  • 2
  • 18
  • 28