This is a very straightforward question, and I apologize if it is a repeat. All I want to know is if there is any general method for determining how efficient the most efficient algorithm for some problem is, in terms of time. Barring that, are there any specific methods used that have accomplished the same for a particular problem? If this is not possible in general or at all what are the hurdles to this, and is there any research along these lines?
1
-
1$\begingroup$ This is possible, but lower bounds are usually not so easy. When doing so, you must always specify a model of computation. An easy example is the sorting lower bound for the decision tree model. I think the same question was asked some time ago, but I am unable to find that question right now... $\endgroup$– JuhoCommented Jun 1, 2015 at 5:16
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Note that there is a problem with no maximally efficient algorithm.
The problem "Is it the case that x has an even number of 1s and
the Turing machine M halts within length(x) steps?" is such that
$\:$ if M halts then the problem takes linear time to solve, since for inputs whose length exceeds
$\:$ the amount of time it takes for M to halt, the algorithm will have to look at each bit of x
$\;\;\;\;$ and
$\:$ if M does not halt then the problem can be solved
$\:$ in constant time, since the answer is no for all x
.
Therefore, deciding how efficient the most efficient algorithm for some problem is, to the
extent that makes sense, is at least as hard as the halting problem. $\:$ On the other hand,
you may be interested in the circuit minimization problem and/or DFA minimization.