3
$\begingroup$

If I understand correctly, the complexity of solving a computational problem is defined in terms of which instance $I$ of the problem, what size $n$ of the problem instance, and what algorithm $A$ for solving the problem instance.

Is the complexity of the problem at a given size $n$ of the problem instance defined as $$ \min_A \max_{I\in \{\text{instances of size }n\}} \text{complexity}(A,I,n)? $$ Note that the solution to the above optimization $A^*(n)$ and $I^*(n)$ are both functions of instance size $n$.

Or is the complexity of the problem defined for some same algorithm for all the problem instances and all sizes of the problem instances?

Or is the complexity of the problem defined for some same instance for all the algorithms that solve the problem and all the problem instance sizes?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ This question can probably be answered by picking up any textbook on the topic and reading the definition. $\endgroup$
    – Raphael
    Oct 5, 2012 at 13:43
  • 2
    $\begingroup$ @Raphael, is there a point in the above comment, other than dis-encouraging people to ask questions?! $\endgroup$
    – Ran G.
    Oct 5, 2012 at 14:41
  • 1
    $\begingroup$ It is intended to encourage better questions, which are more likely to be unearthed after a study of basic material. Questions like "how is defined" are "boring" (and that does not mean they should not be asked!); questions like "why is it defined thus?" or "Is definition <mydef> equivalent?" are more interesting. $\endgroup$
    – Raphael
    Oct 5, 2012 at 19:34

1 Answer 1

Reset to default
6
$\begingroup$

You are missing one thing, namely that the optimal algorithm and worst instance are not simply functions of the instance size. Also, I am not sure that minimising/maximising algorithm and instance independently of each other is doing the right thing.

The complexity of a problem is the complexity of an optimal algorithm solving the problem in the chosen machine model. It's as simple as that, but of course we have to define what "optimal algorithm solving the problem" means. Note that we have to fix the machine model (in particular what to count, see below), as complexities can differ between models.

First, "solving the problem" is clear: for all inputs (that are instances of the problem), the algorithm should give the correct answer, i.e. terminate and produce the correct result, or don't terminate. Let's denote the set of all algorithms that solve problem $P$ with $\newcommand{\Alg}[1]{\mathsf{Alg}_{#1}}\Alg{P}$.

Second, what is the "complexity" of an algorithm? There are many ways to investigate runtime; complexity theory has defaulted to worst-case time and Landau classes. Formally, we define the (worst-case) runtime function of some algorithm $A$ to be

$\qquad \displaystyle T_A(n) = \max \{ T_A(x) \mid x \in I_P, |x|= n \}$

where $I_P$ is the set of instances of the problem $P$ (which $A$ solves) and $T_A(x)$¹ is the runtime of $A$ on input $x$² (in clock cycles, state transitions, whatever fits your machine model). Now, the complexity of $A$ is the asymptotic growth of $T_A$. For example, if $T_A(n) = 17n^2 - 5n + 13$, we would say "The complexity of $A$ is $\Theta(n^2)$".

Finally, an optimal algorithm (for $P$) is an algorithm with minimal complexity (among all algorithms in $\Alg{P}$)³.

  1. We abuse notation here: depending on its parameter, $T_A$ means different things. It is usually done this way, though, and we don't need the runtime on individual inputs later on.
  2. Let's assume for the moment that we deal only with deterministic algorithms. Otherwise, there may be many different runtimes for a given input. In that case, we would choose the runtime of the longest computation; see here for reasons why.
  3. Note that Landau-$O$ implies a partial order on functions: $f \leq g \iff \exists c \in \mathbb{N}.\,\limsup\limits_{n \to \infty} \frac{f(n)}{g(n)} \leq c$.
Improve this answer
$\endgroup$
18
  • $\begingroup$ I would say that an an optimal algorithm for a problem $P$ is an algorithm whose complexity (measured using $O$ notation) matches the lower bound associated to the intrinsic complexity of the problem $P$ (measured using the $\Omega$ notation) if this lower bound is known, and, otherwise, an algorithm with minimal complexity among all of the known published algorithms solving $P$. In the latter case, the optimality is only temporary and a better algorithm may be published later. $\endgroup$
    – Massimo Cafaro
    Oct 5, 2012 at 15:12
  • $\begingroup$ Note that the definition I formulate does not contain any statement about "known" algorithms. If we don't know an optimal algorithm or we don't know whether the best known algorithm is optimal, we simply don't know the problem's complexity. That does not change the complexity, and it does not affect its well-definedness. (The "intrinsic" complexity equals the complexity of an optimal algorithm. In fact, it is defined that way; or how would you define it otherwise?) $\endgroup$
    – Raphael
    Oct 5, 2012 at 19:37
  • $\begingroup$ @Raphael With respect to footnote (2), what algorithm has infinite expected run-time? $\endgroup$
    – Joe
    Oct 5, 2012 at 21:49
  • $\begingroup$ @Joe I don't understand the question. The footnote does in no way relate to expected runtime. $\endgroup$
    – Raphael
    Oct 5, 2012 at 22:00
  • $\begingroup$ @Raphael It relates to expected running time because you suggested minimum running time as an alternative measure of running time. Consider flipping a coin until you get heads. What's a reasonable measure of the number of flips? 1 (the minimum) and $\infty$ (the theoretical maximum) both sound sub-optimal to me. $\endgroup$
    – Joe
    Oct 5, 2012 at 22:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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