<p>I was reading Scott Aaronson's <a href="http://www.scottaaronson.com/blog/?p=1697#comments" rel="nofollow noreferrer">blog</a>, and one of the comments sparked a question.</p>

<p>"if P!=NP, this would be a general, conceptual result, so you’d expect the proof to be explanatory and in particular human-scaled. If P=NP, it could be 'an accident' and the reason is simply that there is some astronomic but polynomial time algorithm for SAT, an algorithm which humans might never grasp."</p>

<p>Problems with this specific argument aside, it seems that many proofs are best made by <a href="https://math.stackexchange.com/questions/263657/is-a-counterexample-considered-a-rigorous-proof-that-a-property-is-not-true">counterexamples</a>, and often these counterexamples are simple enough that it's possible they could be semi-randomly generated by a computer, then automatically checked (say with an <a href="http://en.wikipedia.org/wiki/Interactive_proof_system" rel="nofollow noreferrer">Interactive Proof</a>).</p>

<p>This is also true with algorithms - there are many procedures for checking if an algorithm works for solving a problem (IE: <a href="http://en.wikipedia.org/wiki/Graph_isomorphism_problem" rel="nofollow noreferrer">Blum and Kannan's</a> procedure for the Graph Isomorphism Problem) efficiently, without providing the algorithm itself.</p>

<p>I recognize you have many approximation algorithms that use this very principle to give near/if not optimal answers, but I'm asking about the case where typically such a search isn't academically productive because of how uncommon a randomly generated correct result occurs.</p>

<p><strong>Are there any significant proofs/efficient algorithms that have been randomly generated, potentially far ahead of the theoretical understanding for why those counterexamples exist? Or provided a helpful background that created motivation for building the knowledge-base for that understanding?</strong></p>

<p>The main reason I'm asking is because I've never head of such a result, and am wondering how commonly this occurs (thus if it's a viable assumption it can occur).</p>

CC BY-SA 3.0
2014-03-07T03:35:20.607Z
see eg [genetic algorithms](http://en.wikipedia.org/wiki/Genetic_algorithm) / [genetic programming](http://en.wikipedia.org/wiki/Genetic_programming) which have many remarkable successes & imho are still largely unexplored but there seems to be some widespread avoidance going on....another possibility/untapped wildcard is [machine learning](http://stats.stackexchange.com/questions/73801/machine-learning-applications-in-number-theory)...
vzn
CC BY-SA 3.0
2014-03-07T03:39:28.360Z
That's true, such as their success in the [Sorting Network Problem](http://en.wikipedia.org/wiki/Sorting_network). I suppose I intended ("isn't academically productive") to be asking about problems that don't generally have an optimization structure, and instead have many nearly equally wrong answers and potentially one or two very difficult to find counterexamples (think factoring).
Phylliida
CC BY-SA 3.0
2014-03-07T03:50:07.897Z
That machine learning example was really interesting, thanks. Do things like that happen often?
Phylliida
CC BY-SA 3.0
2014-03-07T15:57:12.640Z
yw. this field (which is somewhat crosscutting and includes [automated thm proving](http://vzn1.wordpress.com/2013/05/03/adventures-and-commotions-in-automated-theorem-proving/)) has some isolated breakthroughs over decades, there are somewhat rare but striking examples. recent notable/high visibility example, [Erdos discrepancy problem advance](http://vzn1.wordpress.com/2014/02/14/great-moments-in-empiricalexperimental-mathtcs-research-breakthough-sat-induction-idea/) along with other recent examples (eg sorting networks). might refmt/write up as answer later. more detail in [chat]
vzn
CC BY-SA 3.0
2014-03-08T13:34:25.983Z
I am going to disagree with the premise of the question here. There are very few algorithms that work because of some "accident", and the chances that an algorithm solves NP-complete problems "by accident" seem to me roughly as small as the chances that some formal manipulation of expressions proves P ≠ NP "by accident".
Peter Shor 
CC BY-SA 3.0
2014-03-08T19:13:09.843Z
That makes sense, and is why I included "problems with this argument aside." Thanks too, "very few algorithms that work because of some 'accident'" answers what my question was mostly addressing.
Phylliida
CC BY-SA 3.0
2014-03-08T19:20:58.803Z
As an aside I really hope that it's not "by accident," a collaborative breakthrough that happens in multiple places at once and that's understandable using current research levels seems like what would probably be best for society, since that would allow for implementation of better crypto algorithms once it started becoming apparent that P probably equals NP, and allow for a pretty thorough understanding of many physical limits if P!=NP (assuming it's not independent of ZFC).
Phylliida
<big-picture><randomness><proofs>
Randomly Discovered Algorithm/Counterexample
Phylliida
# Randomly Discovered Algorithm/Counterexample

(Asked by: username_0 on 2014-03-07)

I was reading Scott Aaronson's [blog](http://www.scottaaronson.com/blog/?p=1697#comments), and one of the comments sparked a question.

"if P!=NP, this would be a general, conceptual result, so you’d expect the proof to be explanatory and in particular human-scaled. If P=NP, it could be 'an accident' and the reason is simply that there is some astronomic but polynomial time algorithm for SAT, an algorithm which humans might never grasp."

Problems with this specific argument aside, it seems that many proofs are best made by [counterexamples](https://math.stackexchange.com/questions/263657/is-a-counterexample-considered-a-rigorous-proof-that-a-property-is-not-true), and often these counterexamples are simple enough that it's possible they could be semi-randomly generated by a computer, then automatically checked (say with an [Interactive Proof](http://en.wikipedia.org/wiki/Interactive_proof_system)).

This is also true with algorithms - there are many procedures for checking if an algorithm works for solving a problem (IE: [Blum and Kannan's](http://en.wikipedia.org/wiki/Graph_isomorphism_problem) procedure for the Graph Isomorphism Problem) efficiently, without providing the algorithm itself.

I recognize you have many approximation algorithms that use this very principle to give near/if not optimal answers, but I'm asking about the case where typically such a search isn't academically productive because of how uncommon a randomly generated correct result occurs.

**Are there any significant proofs/efficient algorithms that have been randomly generated, potentially far ahead of the theoretical understanding for why those counterexamples exist? Or provided a helpful background that created motivation for building the knowledge-base for that understanding?**

The main reason I'm asking is because I've never head of such a result, and am wondering how commonly this occurs (thus if it's a viable assumption it can occur).

**Tags:** big-picture, randomness, proofs
> **Comments:**
> **username_1**: see eg [genetic algorithms](http://en.wikipedia.org/wiki/Genetic_algorithm) / [genetic programming](http://en.wikipedia.org/wiki/Genetic_programming) which have many remarkable successes & imho are still largely unexplored but there seems to be some widespread avoidance going on....another possibility/untapped wildcard is [machine learning](http://stats.stackexchange.com/questions/73801/machine-learning-applications-in-number-theory)...  
> **username_0**: That's true, such as their success in the [Sorting Network Problem](http://en.wikipedia.org/wiki/Sorting_network). I suppose I intended ("isn't academically productive") to be asking about problems that don't generally have an optimization structure, and instead have many nearly equally wrong answers and potentially one or two very difficult to find counterexamples (think factoring).  
> **username_0**: That machine learning example was really interesting, thanks. Do things like that happen often?  
> **username_1**: yw. this field (which is somewhat crosscutting and includes [automated thm proving](http://vzn1.wordpress.com/2013/05/03/adventures-and-commotions-in-automated-theorem-proving/)) has some isolated breakthroughs over decades, there are somewhat rare but striking examples. recent notable/high visibility example, [Erdos discrepancy problem advance](http://vzn1.wordpress.com/2014/02/14/great-moments-in-empiricalexperimental-mathtcs-research-breakthough-sat-induction-idea/) along with other recent examples (eg sorting networks). might refmt/write up as answer later. more detail in [chat]  
> **username_2**: I am going to disagree with the premise of the question here. There are very few algorithms that work because of some "accident", and the chances that an algorithm solves NP-complete problems "by accident" seem to me roughly as small as the chances that some formal manipulation of expressions proves P ≠ NP "by accident".  
> **username_0**: That makes sense, and is why I included "problems with this argument aside." Thanks too, "very few algorithms that work because of some 'accident'" answers what my question was mostly addressing.  
> **username_0**: As an aside I really hope that it's not "by accident," a collaborative breakthrough that happens in multiple places at once and that's understandable using current research levels seems like what would probably be best for society, since that would allow for implementation of better crypto algorithms once it started becoming apparent that P probably equals NP, and allow for a pretty thorough understanding of many physical limits if P!=NP (assuming it's not independent of ZFC).  

---

## 0 answers

