Timeline for Examples of Super-polynomial time algorithmic/induction proofs?
Current License: CC BY-SA 2.5
2 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 31, 2010 at 14:31 | comment | added | miforbes | Thanks, I am aware of Papadimitriou's various inefficient proofs of existence, but I consider these more of a brute-force type of proof in the sense that the algorithms themselves don't really establish the existence of the desired object - it is the various lemmas (parity, etc) that he uses to establish the existence. The algorithms sort of fall out in a trivial way. Though, perhaps it isn't a meaningful distinction. | |
| Jul 30, 2010 at 22:26 | history | answered | Noah Stein | CC BY-SA 2.5 |