-1

If I understand correctly, the phrase "decision problem" basically means a subset of $\mathbb{N}$. A complexity class is a set of decision problems, ergo it's a set of subsets of $\mathbb{N}$. A decision problem $D$ is in a complexity class $\mathbf{C}$ iff $D \in \mathbf{C}$.

This seems at odds with statements like "$\mathbf{P}$ is the complexity class of decision problems for which solutions can be found in polynomial time." In some sense, every problem is in $\mathbf{P}$. For example, given a problem $D$ for which finding an element is difficult insofar as it takes about a 1 year to do it, but nonetheless possible, there's a perfectly good "instantaneous" algorithm to find an element of $D$. You just pre-compute an element. And sure, it takes a year. But now you have an algorithm that's virtually instantaneous. In particular, when you're asked to find an element, you just give the asker the value you precomputed.

In other words, every decision problem can, in some sense, be solved in $O(1)$ time. So every decision problem is an element of $\mathbf{P}$.

Obviously, this is nonsense, and I have not grasped the basic definitions.

Question. What do the phrases "decision problem" and "complexity class" really mean?

goblin GONE
  • 67,744
  • 1
    Can you write an algorithm for computing $n!$ ? What is its complexity (how many operations does it run before the correct result has been computed) ? What would be the optimal complexity of an algorithm for $n!$ ? What if you are allowed to parallize the algorithm (use $k$ computers in the same time) ? – reuns Oct 16 '17 at 04:15
  • 1
    This should be explained in every textbook on complexity, including many online resources. – Mariano Suárez-Álvarez Oct 16 '17 at 04:55

2 Answers2

2

In a statement like "P is the complexity class of decision problems for which solutions can be found in polynomial time", the problem being solved is not to find an element of the subset of $\mathbb{N}$ given by the decision problem. The problem is: given an arbitrary element of $\mathbb{N}$, determine whether it's in the subset of $\mathbb{N}$ given by the decision problem. You have to be able to give an answer of all elements of $\mathbb{N}$. So (except in the trivial case where the subset is finite or cofinite) you cannot pre-compute all solutions.

Ted
  • 33,788
0

Expanding a bit on what Ted said: A problem $p\subset \mathbb{N}$ is in $\mathsf{P}$ if there exists a Turing Machine* $T$ which, when fed input $n$, outputs $1$ if $n\in p$ and $0$ otherwise, such that the number of steps it takes for $T$ to halt on input $n$ is $O(f(n))$ for $f$ a polynomial.

The reason I star "Turing Machine" is that "Turing Machine" is a bit over-loaded; there are many variants of Turing Machines, so just assume "Turing Machine" means "single-tape deterministic Turing Machine" with alphabet $0,1$, where feeding an input $n$ means feeding in its binary representation.

Of course, $\mathsf{P}$ is pretty well-defined; as long as we encode our natural numbers in a nice-enough way, it won't matter what our alphabet is nor how we encode things. Moreover, we can also change up how the Turing Machine works; for example, it could have two tapes in which a only one head can move at a time, and this wouldn't change whether or not a decision problem is in $\mathsf{P}$ (it could change what the runtime is, but it won't change whether or not the runtime is $O(f(n))$ for a polynomial $f$). (We need to keep deterministic though, as otherwise we would be defining $\mathsf{NP}$.)

Hayden
  • 16,737