I'm wondering if a mathematical set definition has a computational complexity.
For example, assume I have some kind of problem where the solution is given by the positive integers smaller than a given integer $n$:
$M = \{ x | x < n, x \in \mathbb{N} \}$
Could I say this problem can be solved in $\mathcal{O}(n)$ because I could realistically construct an algorithm that yields this result in linear time?
I actually have such an approach in a paper where it makes more sense to define a set than give an (trivial) algorithm that returns this set.
-
1$\begingroup$ In $O(2^n)$ time if you encode $n$ in non-unary, but yes, that makes completely sense. $\endgroup$Ainsley H.– Ainsley H.2022年01月13日 09:59:28 +00:00Commented Jan 13, 2022 at 9:59
-
1$\begingroup$ When you say $\mathcal{O}(n)$ you probably do not mean the $n$ from the defintion of the set but the size of the input. Since your set is finite, it can be decided by a mere table lookup. Depending on your model of computation, the complexity for this can even be less than linear. At any rate, "problems" in complexity theory are sets, so it makes perfect sense to attribute a complexity to them. Not the "set definition has a computational complexity" but the set. $\endgroup$Peter Leupold– Peter Leupold2022年01月13日 10:48:09 +00:00Commented Jan 13, 2022 at 10:48
1 Answer 1
Usually, mathematical definitions are not computational. Informally, mathematics describes the "what", not "how" you compute it.
However, for some problems there is an obvious algorithm deciding them. I would not see an issue with a sentence like this:
The problem $\{x \in \mathbb N,円|,円 x < c\}$ can be decided in $O(n)$ for all constants $c$.
Yet, the set definition still does not carry any computational behavior. It's just that it is decidable, and you consider finding a decision procedure with the stated complexity trivial enough for your target audience. The decidability does not depend on how you define it.