I was reading Scott Aaronson's blog, 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, 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).

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 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).

  • $\begingroup$ see eg genetic algorithms / 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... $\endgroup$ – vzn Mar 7 '14 at 3:35
  • $\begingroup$ That's true, such as their success in the Sorting Network Problem. 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). $\endgroup$ – Phylliida Mar 7 '14 at 3:39
  • $\begingroup$ That machine learning example was really interesting, thanks. Do things like that happen often? $\endgroup$ – Phylliida Mar 7 '14 at 3:50
  • $\begingroup$ yw. this field (which is somewhat crosscutting and includes automated thm proving) has some isolated breakthroughs over decades, there are somewhat rare but striking examples. recent notable/high visibility example, Erdos discrepancy problem advance along with other recent examples (eg sorting networks). might refmt/write up as answer later. more detail in Theoretical Computer Science Chat $\endgroup$ – vzn Mar 7 '14 at 15:57
  • 1
    $\begingroup$ 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". $\endgroup$ – Peter Shor Mar 8 '14 at 13:34

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.