1
$\begingroup$

Ultimately, when you compile them to machine code, algorithms are just 1's and 0's. So then - could you brute force the genesis, and thus the discovery of new, useful algorithms? Say, in pursuit of polynomial time algorithms for NP-complete problems.

Of course, rather than pure brute force, perhaps some intelligent force could be applied as a refinement.


My back-of-the-napkin-ish attempt to answer the question. Just an exercise; I don't really trust it.

  1. In theory, yes - absolutely. The question is whether, in practice, it could be done in a reasonable amount of time in a cost-effective manner.
  2. The amount of possible permutations of 1's and 0's is $2^n$ where n = the number of bits in your code.
  3. Roughly how many bits does it take to write algorithms? To answer this question, I googled for a quick sort implementation in c, and compiled it to machine code. The result was about 10,000 bytes. So 80,000 bits. Let's say 100,000 bits for a round number.
  4. There are $2^{100,000} = 10^{30,103}$ permutations of 1's and 0's.
  5. You'd have to test each of these permutations. Let's say it takes 1 minute to test a permutation of 1's and 0's. Then that'd take $10^{30,097}$ years to finish testing. No good.
  6. Perhaps the parameters could be tweaked. Let's try just 1,000 bits and 1 second to test each permutation. $2^{1000} = 10^{301}$ permutations. That'd take $10^{295}$ years.
  7. Even if we used a lot of computing power, that'd still only cut the exponent down by 5 or 10, maybe. So ultimately, it seems impractical to actually brute force. The question then becomes whether we can combine intelligent force with brute force in algorithm generation.
  8. Even though brute force seems impractical, I wonder if future generations will have insane computational power that we would never dream of. If so, brute forcing algorithm generation may be possible. Of course, they may have figured out all the algorithms by then.
$\endgroup$
  • 1
    $\begingroup$ You may be interested in the work of Nick Smallbone, Moa Johansson et al. (Google Scholar helps you.) They have been working on automatically proving properties about code; I think the method can well work in reverse. $\endgroup$ – Raphael Apr 16 '17 at 9:28
  • $\begingroup$ In a 2003 DISC paper Yoah Bar-David and Gadi Taubenfeld reported on some success in the area. Automatic Discovery of Mutual Exclusion Algorithms $\endgroup$ – Kai Jun 12 '17 at 3:01
3
$\begingroup$

You are correct in saying that algorithms are no more than a sequence of strings. However, you should make the distinction between syntactic and semantic properties of the algorithm. Syntactic properties are those relating to the actual code, e.g. what is the length of the program? how many "while" loops does it contain? Semantic properties are related to what the program actually does, e.g. is there some input that would cause this program to go into an infinite loop?

The problem you encounter in your suggestion is that almost every interesting semantic property is undecidable, meaning that even with unlimited resources (time/memory) you cannot algorithmically reason about this property just by looking at the source code. So in fact, the situation is worse than what you think. Even the craziest hardware won't help us, since such tasks are impossible for a computer.

As a side note, suppose your situation was better, and you try to cope with some decidable problem which has an exponential lower bound (i.e. all algorithms for this problem would require exponential time, not just brute force search, even the "smart" ones). Again, better hardware won't help you. For some intuition regarding your parameters, you have $\approx 10^{80}$ atoms in the universe, so performing this amount of operations is hopeless. What you need is a smarter algorithm, but we started with a problem that unfortunately has an exponential lower bound.

$\endgroup$
  • 1
    $\begingroup$ "The problem you encounter in your suggestion is that almost every interesting semantic property is undecidable, meaning that even with unlimited resources (time/memory) you cannot algorithmically reason about this property just by looking at the source code." -- While technically true, this may not be relevant to practice as it may seem. *Semi-*decision procedures may well exist, and heuristics that prove or disprove many properties quickly. In fact, the whole body of research around (semi-)automatically proving poperties of programs deals with that. $\endgroup$ – Raphael Apr 16 '17 at 9:30
  • $\begingroup$ Very useful answer. The OP says "Let's say it takes 1 minute to test a permutation." Likely the OP does not know that testing does not guarantee correctness. A usual programmer's mistake. If there is no proof that an algorithm is correct, IMHO, it should not be considered correct. (And this requirement must not be dropped, otherwise any algorithm is okay for any problem, and we can just pick any existing algorithm without even starting brute force.) $\endgroup$ – beroal Apr 16 '17 at 9:44
  • $\begingroup$ re: "even with unlimited resources (time/memory) you cannot algorithmically reason about this property just by looking at the source code. So in fact, the situation is worse than what you think. Even the craziest hardware won't help" and "testing does not guarantee correctness @beroal". That makes sense. However - perhaps proof isn't the only useful goal (sorry, I didn't mention this in my OP). If we test an algorithm on an input and it performs in polynomial time, perhaps we humans could reverse engineer things from there. Thoughts? $\endgroup$ – Adam Zerner Apr 16 '17 at 16:15
  • $\begingroup$ The intuition of there being $10^{80}$ atoms in the universe was very helpful - thanks. $\endgroup$ – Adam Zerner Apr 16 '17 at 16:28
  • 1
    $\begingroup$ @Ariel We can enumerate programs and correctness proofs; interleave the two enumerations and run until you find a matching pair. Unless there are problems that are only solved by programs that can not be proven correct, this is a semi-"decision" procedure. $\endgroup$ – Raphael Apr 17 '17 at 11:08
0
$\begingroup$

It seems that you answered your question. As you stated in 2 your search space has the size of $2^n$, which obviously leads you towards a non polynomial time. Even if you will use some kind of a smart search on this problem that, for example, reduces the search space by the factor of 100 you will still end with a non polynomial size of the search space.

Unless P=NP, you have an algorithm that reduces the search space exponentially or some kind of hardware that works in a totally different way (for example a quantum computer. I don't know if it can help solve this particular problem but there are other problems that have similar complexity that it will solve in reasonable time) you won't be able to solve this problem in a reasonable time.

$\endgroup$
  • $\begingroup$ I don't think it's self evident that the $2^n$ space of potential solutions is impractical. It seems to me to depend on all of those parameters. In particular, I don't know much about high performance computing, and where the field is headed. Maybe with enough power it really is doable. I also don't know much about what kinds of intelligent improvements could be made. Or whether my choice of n was sensible. $\endgroup$ – Adam Zerner Apr 16 '17 at 7:51
  • $\begingroup$ It's not about hardware and how many machines do you have it's about your algorithm complexity. If you preform some kind of brute force search you can't complete it on any machine unless the number of bits is really small. There are many problems with your proposal besides it being too expansive. For a specific problem you will get to a specific answer of this problem but not a general one. Example: You want to sort an array, you may find the fastest way to sort this specific array but it won't work a different array. $\endgroup$ – Andrey Gurevich Apr 16 '17 at 8:41
  • $\begingroup$ The question is about finding polynomial time algorithms. It's not, in principle, a problem if finding the algorithm takes a long time, since you only need to find it once. Note also that P-vs-NP doesn't have much impact on exponential search problems: you shouldn't associate NP with exponential time, because that's not what it is: we believe that NP is strictly weaker than EXP. $\endgroup$ – David Richerby Apr 16 '17 at 14:58

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.