3 ms·
Call me naive but, wouldn't feeding it random input and expected output sorted by existing and proven (but slower) sorting algorithms do the trick?
by Cthulhu_ 6y ago
Call me naive but, wouldn't feeding it random input and expected output sorted by existing and proven (but slower) sorting algorithms do the trick?
- Scea91 6y agoFor an exact proof of correctness no, because that would only show the algorithm is correct for a selected set of input-output pairs. However, it is true that validating it for a very large number of inputs and outputs has value. This is not uncommon even in mathematics. For example, Goldbach's Conjecture (https://www.wikiwand.com/en/Goldbach%27s_conjecture https://www.wikiwand.com/en/Goldbach%27s_conjecture) has not been proven but has been shown to hold for all integers less than 4 × 10^18
- exdsq 6y agoThis is done! The existing correct algorithm is called the oracle and it’s used to validate the generated algorithm. There’s some cool work on using neural program induction in compilers to try generate faster implementations based off the ‘oracle’ program that’s being compiled.
- algo_trader 6y ago> neural program induction in compilers to try generate faster implementations Can u provide more details? I am familiar with garden-variety ML-optimization-of-combinatorical-space in compilers. How would u even "measure" the expected performance unless these are gradual greedy changes