2
$\begingroup$

Are there standard techniques to show that no algorithms exist for given complexity constraints?

For example, consider the following problem. The input is a list of items with exactly one duplicate, and you wish to find the duplicate item.

How do you formally prove that there cannot be an algorithm that does this in constant space and linear time?

$\endgroup$

closed as off-topic by Sasho Nikolov, Mohammad Al-Turkistany, Emil Jeřábek supports Monica, R B, Jan Johannsen Mar 13 '17 at 8:33

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Sasho Nikolov, Mohammad Al-Turkistany, Emil Jeřábek supports Monica, R B, Jan Johannsen
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ Adversary argument? $\endgroup$ – Hsien-Chih Chang 張顯之 Mar 12 '17 at 4:26
  • $\begingroup$ I don't see how to solve this problem in constant space with any amount of time, since you need superconstant space just to write down the answer.... But anyway one answer to your question is information theory, also communication complexity which is closely related. $\endgroup$ – usul Mar 13 '17 at 5:40
2
$\begingroup$

See this lower bound for sorting, for example: http://planetmath.org/lowerboundforsorting

You typically need to assume something about the algorithm's access to the input data. In this case, the assumption is that the algorithm sorts via pairwise comparisons. Any such algorithm must make at least $\Omega(n\log n)$ such comparisons. This is because the pairwise comparisons effectively induce a binary tree on $n!$ leaves -- one leaf for each possible input ordering. Such a tree must have depth $\Theta(\log(n!))=\Theta(n\log n)$.

Note that in a different data access model, algorithms can achieve linear-time sorting: https://en.wikipedia.org/wiki/Radix_sort

Obiously, faster than linear time is impossible, since you have to at least read all of the inputs.

$\endgroup$
  • 1
    $\begingroup$ This is not entirely correct for the example. You do not need to sort the elements in order to find the single duplicate. You can do it in linear time easily, but you need at least two pointers, each of size of log n bits. $\endgroup$ – PsySp Mar 12 '17 at 17:11
  • $\begingroup$ Ah, ok -- was answering a different part of the question, before the "For example". I think the answer does offer some insight for that part, but it's a judgement call. $\endgroup$ – Aryeh Mar 12 '17 at 17:25
2
$\begingroup$

What you are asking for is methods in proving lower bounds on the computational complexity (measured in space, time, etc) of given computational problems, and the answer is mostly that we have made very little progress on general methods for this and that is essentially the entire subject of complexity theory.

That being said, if you're more interested in estimates that are almost certainly going to be useful, you can use the tool of the reduction which will essentially place your problem in a partial order representing the difficulty of problems, allowing you to then think about how hard it is relative to the other problems we study, given some granularity of reduction (in the link, reductions in FP).

$\endgroup$

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