# Formally proving no algorithm exists [closed]

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?

• Mar 12, 2017 at 4:26
• 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.
– usul
Mar 13, 2017 at 5:40

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.

• 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. Mar 12, 2017 at 17:11
• 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. Mar 12, 2017 at 17:25

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).