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

Question

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?

Answer 1

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.

Answer 2

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}$.)