> I feel like future research will focus on finding the line that divides the "tractable" problems from the "intractable" ones. IIRC, there's some research abo

> I feel like future research will focus on finding the line that divides the "tractable" problems from the "intractable" ones. IIRC, there's some research about "Phase transitions in Computation Complexity" that seems to be what you are looking for: http://www.lsv.fr/Events/fmt2012/SLIDES/moshevardi.pdf http://www.lsv.fr/Events/fmt2012/SLIDES/moshevardi.pdf (I think I saw that talk at Youtube a long time ago, but I can't find it now)