0
$\begingroup$

As programmers, we are always trying to find the most efficient space and time complexity solutions to algorithms.

Is it forseeable in the future that we have languages or techniques such as AI/machine learning to automatically find such optimum solutions to any generic algorithm?

$\endgroup$
5
  • 4
    $\begingroup$ Possible duplicate: we know that no algorithm can solve this task, optimizing compilation. $\endgroup$
    – Raphael
    Oct 22, 2016 at 16:17
  • $\begingroup$ Also related. $\endgroup$
    – Raphael
    Oct 22, 2016 at 16:21
  • $\begingroup$ Note that it's not even computable to (always) find the $\Theta$-class if the running time! $\endgroup$
    – Raphael
    Oct 22, 2016 at 16:22
  • 1
    $\begingroup$ Your first sentence is completely wrong. First, "solutions to algorithms" doesn't make much sense. Second, we look for solutions that are correct, readable, and maintainable, while being acceptable in their time and space requirements. "Optimal" is rarely a requirement or priority (sometimes it is). $\endgroup$
    – gnasher729
    Oct 23, 2016 at 21:19
  • $\begingroup$ My main point was wanting to know if finding the most optimal solution was possible in an automated manner. If so, who wouldn't want to find the most optimal solutions. You are needlessly focusing on the first sentence instead of the bigger question I am posing here. $\endgroup$
    – Samar
    Oct 23, 2016 at 23:51

1 Answer 1

4
$\begingroup$

No.

With all the hype about AI/Machine learning, sometimes people forget that there are known limitations to computers, which can be proven, so it doesn't matter how fast your computer is, how sophisticated is your neural net, you just cant do it.

I'll try to address your specific question. First, you have to define exactly what is the task that you expect your AI algorithm to solve. Suppose your input is a description of the problem, given in the form of an encoding of a Turing machine $\langle M\rangle$ which solves it, or as a valid code in your favorite programming language. Now, say we want to output an equivalent program, with optimal (asymptotic) time complexity.

The decision version corresponding to your problem is, given a program in your language, decide if there exists an equivalent program with better (asymptotic) time complexity.

This is not possible for any computer, or in more technical terms, this language is undecidable. We can reduce the halting problem to the above in the following way:

Given a pair $(\langle M \rangle,w)$, Let $M_w$ be the machine which, given input $x$, runs $M$ on $w$ for $|x|$ steps. If $M$ halted then $M_w$ accepts iff $x$ is a palindrome. If $M$ didn't halt within $|x|$ steps, $M_w$ rejects. We can build $M_w$ such that $M_w$ runs in $O(n^2)$ time.

If $M$ halts on $w$ after $n$ steps, then $L(M_w)=\left\{x \big| |x|\ge n \land \text{x is a palindrome}\right\}$, otherwise $L(M_w)=\emptyset$. Since we know that checking whether a string is a palindrome requires $\Omega(n^2)$ time on a single tape Turing machine, then if $M$ halts on $w$, $M_w$ decides $L(M_w)$ with optimal time complexity. Otherwise it doesn't (the empty language can be decided in constant time, just output "no" without even reading the input). This means that $M$ halts on $w$ iff $M_w$ has optimal time complexity.

This shows that for general programs, this task is hopeless. Perhaps, for a specific subset of programs, you can decide optimality, and this doesn't necessarily mean using some fancy AI algorithm, see Program optimization.

$\endgroup$
2
  • $\begingroup$ Duplicate? $\endgroup$
    – Raphael
    Oct 22, 2016 at 16:17
  • $\begingroup$ Seems so (of the question, at least). In light of the comment to your answer, I want to add that when talking about the decision version, the palindrome part is necessary (we need to add something other than simple simulation). If $M$ halts in $n$ steps, and $M_w(x)$ only simulates $M$ on $w$ for $|x|$ steps, then we can improve it's running time to $O(1)$ (check whether the input is of length $\ge n$). $\endgroup$
    – Ariel
    Oct 22, 2016 at 16:45

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