3
$\begingroup$

Isn't it possible to prove it by defining some problem that can be solved in $f(n)^2$ in the worst case due to its output always being $f(n)^2$ characters so that it won't be solvable in $f(n)$? Where am I wrong?

$\endgroup$
6
$\begingroup$

The output size does not scale with (time) complexity of problems in general. In fact, complexity theorists are largely interested in decision problems for which the output will either be 0 or 1.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ What do you mean by "The output size does not scale with (time) complexity of problems in general" Can you expand your answer a bit? $\endgroup$ – Prro Bam Sep 22 at 23:33
  • 1
    $\begingroup$ It's in the second sentence. Complexity theory is largely about decision problems where the output size does not depend on the input size or the running time of an algorithm (if one even exists!). Actually, the wikipedia page for the THT is stated explicitly in terms of decision problems. What you state in the OP is not wrong, it is just not useful to complexity theorists. $\endgroup$ – Watercrystal Sep 22 at 23:42
  • $\begingroup$ Do you think that the original paper about the theorem phrased it in terms of decision problems or something similar? $\endgroup$ – Prro Bam Sep 23 at 0:04
  • 1
    $\begingroup$ Yes. Wikipedia gives a reference to the original paper which states the theorem in terms of binary sequences, which are basically decision problems. $\endgroup$ – Watercrystal Sep 23 at 0:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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