1
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ In $O(2^n)$ time if you encode $n$ in non-unary, but yes, that makes completely sense. $\endgroup$
    – Pål GD
    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$ Jan 13, 2022 at 10:48

1 Answer 1

0
$\begingroup$

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.

$\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.

Not the answer you're looking for? Browse other questions tagged or ask your own question.