8
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – mdxn
    Sep 30, 2013 at 18:03
  • $\begingroup$ 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. $\endgroup$
    – user1338
    Sep 30, 2013 at 19:03
  • $\begingroup$ Although the ordinary English word "descriptive" doesn't mean "using logic/finite model theory", the technical term "descriptive complexity" does mean that. $\endgroup$
    – David Richerby
    Sep 30, 2013 at 20:23
  • $\begingroup$ Ok. I'll change the question. $\endgroup$
    – user1338
    Sep 30, 2013 at 20:28
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Marzio De Biasi
    Sep 30, 2013 at 21:49

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

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