hi all. recently Backurs/ Indyk just got a paper accepted into STOC 2015 connecting the Strong Exponential Time Hypothesis (“SETH”) with tight bounds on computing edit distance. the latter has many applications across CS and also plays a big role in bioinformatics and computational biology wrt DNA sequences where it relates to natural alterations, ie more specifically “biologically occurring genetic processes”—eg *even occuring in our own bodies… and surely cant get more “applied” than that!*

there is some buzz/ excitement on this result as this is regarded as something of a breakthrough. it reminds me of the concept of “the microcosm reflects the macrocosm and vice versa” aka/ in short, “as above, so below”. a polynomial time algorithm speed (“the small”) seems to have major implications for speed of NP complete problems wrt exponential time (“the large”) and vice versa.**[a]**

⭐ ➡ and moreover/ further, near-dramatic connection/ exhibition/ manifestation/ confirmation of an apparent deep/ recurring principle/ theme/ “design pattern” in CS, interconnection/ interdependency of upper and lower bounds. at times upper and lower bounds seems like the *yin and yang* of TCS… 💡 😮 ❤

oh, but alas, *not exactly;* some fine print, its not quite as strong as one might hope. SETH implies P≠NP but based on current knowledge, SETH false could have no implication on P vs NP. a near miss? maybe this line of study might have even more direct implications on proving P≠NP with more study? (ie proving tight lower bounds on edit distance implying P≠NP?)

anyway it gives me an excuse to unleash a big pile of links on one of my favorite subjects, the CS “time/space hierarchy/ continuum” (doesnt it just sound so exotic, like something out of star trek or the matrix?) 😎 😀

there have also been neat recent results on L vs P connected to intersection nonemptiness of DFAs by Wehar. worked on this problem myself years ago empirically and had suspicions it might be connected to deep complexity class separations and its really great to see this confirmed. Wehar is active on cstheory.se & has even chatted some about his paper & other topics, a big highlight for me. hi MW!**[b]** 🙂

one of my favorite topics in CS & P vs NP is the transition point which think likely will play a big role in any P vs NP proof, but alas research on the subject seems to have dropped off in recent years, although there is still a lot of interest and mass amounts of papers written on the subject. Moshe Vardi recently posted a comprehensive youtube lecture that showed up on reddit. it seems a nearly striking/ gaping omission to me that wikipedia has no entry on the subject, which connects/ crosscuts deep CS to physics. any takers?**[c]**

natural proofs by razborov/ rudich (2007 Nevanlinna prize) has a big role in P vs NP study and there has been some newer ideas on it from Chow leading to some glimmers of reexamination lately. natural proofs is considered a so-far nearly insurmountable barrier against P vs NP proofs and its great to see some deeper analysis/ rethinking on the subject.**[d]**

**a. Backurs, Indyk, SETH vs edit distance/ P vs NP**

- 1. [1412.0348] Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
- 2. 40-year-old algorithm proven the best possible
- 3. Longstanding problem put to rest | MIT News
- 4. Puzzling Evidence | Gödel’s Lost Letter and P=NP
- 5. How Hard is to Compute the Edit Distance – Giovanni Pighizzini
- 6. Fast string correction with Levenshtein automata – Springer
- 7. cc.complexity theory – Statements that imply $\mathbf{P}\neq \mathbf{NP}$ – Theoretical Computer Science Stack Exchange
- 8. cc.complexity theory – Why is P vs. NP so hard? – Theoretical Computer Science Stack Exchange
- 9. soft question – Analogues of P vs. NP in the history of mathematics – MathOverflow
- 10. logic – Solving P vs NP with computer – Mathematics Stack Exchange
- 11. For 40 years, computer scientists looked for a solution that doesn’t exist / Boston Globe
- 12. A New Map Traces the Limits of Computation/ Quanta mag

**b. L vs P**

- 1. Logspace vs Polynomial time « My Brain is Open
- 2. cc.complexity theory – Separating Logspace from Polynomial time – Theoretical Computer Science Stack Exchange
- 3. cc.complexity theory – What are the compelling reasons for believing $L\neq P$? – Theoretical Computer Science Stack Exchange
- 4. compression of a turing machine run sequence – MathOverflow
- 5. Hardness Results for Intersection Non-Emptiness / Wehar
- 6. cc.complexity theory – Does L=P imply any new complexity class separations? – Theoretical Computer Science Stack Exchange
- 7. complexity theory – Switching Lemma and AC0 reductions between SAT problems – Computer Science Stack Exchange

**c. transition**

- 1. Phase transition behavior / Walsh
- 2. Phase transitions in NP-complete problems: a challenge for probability, combinatorics, and computer science / Moore
- 3. computational complexity – Is it easy to produce hard-to-color graphs? – MathOverflow
- 4. cc.complexity theory – Which SAT problems are easy? – Theoretical Computer Science Stack Exchange
- 5. cc.complexity theory – Examples of hardness phase transitions – Theoretical Computer Science Stack Exchange
- 6. cc.complexity theory – Phase Transitions in NP Hard Problems – Theoretical Computer Science Stack Exchange
- 7. cc.complexity theory – Ranking the Difficulty of NP Hard Problems in Practice – Theoretical Computer Science Stack Exchange
- 8. Highest Voted ‘phase-transition’ Questions – Theoretical Computer Science Stack Exchange
- 9. popularity contest – So obviously, P = NP – Programming Puzzles & Code Golf Stack Exchange
- 10. Video: Moshe Vardi, “Phase transitions and computational complexity”

**d. natural proofs**

- 1. 2007 Godel Prize
- 2. Almost-natural proofs Timothy Y. Chow
- 3. Almost-Natural Proofs Timothy Y. Chow (arxiv)
- 4. cc.complexity theory – Barriers and Monotone Circuit Complexity – Theoretical Computer Science Stack Exchange
- 5. cc.complexity theory – Has there been any result which does not have any Natural Proofs? – Theoretical Computer Science Stack Exchange
- 6. cc.complexity theory – Random monotone function – Theoretical Computer Science Stack Exchange
- 7. cc.complexity theory – Scope of natural proofs barrier – Theoretical Computer Science Stack Exchange
- 8. computational complexity – Razborov’s response to Almost Natural Proofs – MathOverflow
- 9. Gödel Prize – Wikipedia, the free encyclopedia
- 10. How not to prove that P is not equal to NP | Gowers’s Weblog
- 11. Moshkovitz Natural Proofs lecture notes
- 12. Natural proof – Wikipedia, the free encyclopedia
- 13. Natural Proofs Explained Chris Calabro
- 14. On the method of approximations, Razborov
- 15. Program for Barriers in Computational Complexity Workshop
- 16. Razborov and Rudich’s natural proofs argument | Gowers’s Weblog
- 17. What is … a Natural Proof? Timothy Y. Chow
- 18. Who’s Afraid of Natural Proofs? | Gödel’s Lost Letter and P=NP

**e. etc**

- 1. We Believe A Lot, But Can Prove Little « Gödel’s Lost Letter and P=NP
- 2. complexity theory – Lower bound on running time for solving 3-SAT if P = NP – Computer Science Stack Exchange
- 3. complexity theory – Why can’t we flip the answer of a NDTM efficiently? – Computer Science Stack Exchange
- 4. intuition – Why doesn’t a time cutoff convert NP problems into co-NP? – Computer Science Stack Exchange
- 5. Relation of Space and Time in Complexity? – Computer Science Stack Exchange
- 6. graphs – Transition coverage for a DFA – Computer Science Stack Exchange
- 7. Computational Complexity: Sizes of DFAs, NFAs, DPDAs, UCFG, CFGs, CSLs.
- 8. ds.algorithms – Polynomial-time algorithms with huge exponent/constant – Theoretical Computer Science Stack Exchange

Pingback: Terence Tao magic breakthrough again with EDP, Erdos Discrepancy Problem, topnotch links | Turing Machine