0
$\begingroup$

If the set $P$ is defined as the set of decision problems that can be solved by a deterministic Turing Machine in polynomial time, and matrix inversion using Gaussian elimination is $O (n^3)$, then how can I relate these two concepts to conclude that inverting a matrix is in $P$?

I suppose I need a way of converting a description of Gaussian elimination into a decision problem? Or maybe I am confused about the fundamentals

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ There are two classifications, classification of the problems by their complexity and the classification of the algorithms by their complexity. The former is usually defined on top of the latter. It is much much harder to determine the former than to determine the latter in general. $\endgroup$ – John L. Jun 19 '19 at 4:23
1
$\begingroup$

how can I relate these two concepts to conclude that inverting a matrix is in $\mathrm{P}$?

You can't. Your question contains two category errors.

  • Complexity classes are classes of problems, not classes of algorithms. The complexity of a problem is the minimum amount of resources that are required to solve that problem, by any algorithm. "Resources" might be time, space, or other more exotic things. "Finding a matrix inverse by Gaussian elimination" isn't a problem: it's an algorithm (Gaussian elimination). The resource usage of any specific algorithm gives you an upper bound on the complexity of the problem that the algorithm solves, but it doesn't tell you anything else. When discussing a particular algorithm, if we're being careful about language, we talk about its running time and its space usage, rather than its complexity.

  • $\mathrm{P}$ is a class of decision problems: problems with yes/no answers. Inverting a matrix isn't in $\mathrm{P}$ for the simple reason that it's not a decision problem. Gaussian elimination shows that matrices can be inverted in polynomial time, so it's in the class $\mathrm{FP}$ of function problems that can be solved in polynomial time. But, again, when being careful, we don't say that it's in $P$. On the other hand, related (but, admittedly rather artificial) problems such as "given a matrix $M$ and an integer $k$, is the $k$th bit of $M^{-1}$ a one?" are in $\mathrm{P}$ (if you're worried about corner-cases, define the answer to be "no" if either $M^{-1}$ doesn't exist, or it exists and has fewer than $k$ bits).

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Gaussian elimination is an algorithm, you can’t frame it as a problem and thus it can’t be in $P$.

But matrix inversion itself is a problem and its decision version is as follows: “does matrix $M$ have an inverse?”

Gaussian elimination then is one possible way to prove that you can always answer that question in polynomial time, therefore matrix inversion is in $P$.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ "Matrix inversion" is a terrible name for the problem "does matrix $M$ have an inverse?" The name "matrix inversion" strongly suggests "find the inverse of matrix $M$ if it exists." If one wishes to talk about the decision problem, one should give it a name that sounds like a decision problem, such as "matrix non-singularity" or "matrix invertability". $\endgroup$ – David Richerby Jun 19 '19 at 9:25
  • $\begingroup$ @DavidRicherby I'm under impression that when we're talking about complexity class membership, it is common to make no distinction between P and FP problems, because the same single trick works for their mutual reduction. $\endgroup$ – Dmitri Urbanowicz Jun 19 '19 at 10:37
  • $\begingroup$ Careful writers distinguish the two, even though they are more or less equivalent. $\endgroup$ – David Richerby Jun 19 '19 at 11:25

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.