3 ms·
I once chased down the paper where that Russian showed lower bounds on circuits couldn't be used to prove P!=NP. The frustrating thing about the paper was that
by joe_the_user 14y ago
I once chased down the paper where that Russian showed lower bounds on circuits couldn't be used to prove P!=NP.
The frustrating thing about the paper was that it lots of references to "what a mathematicians thinks of a proof as" or something like that. IE, it wasn't a formal proof of a general result, didn't claim to be such, but was still taken as a definite word that circuit lower bounds was a dead end for that problem.
I'd chase down the real reference if I had time.
I'm still not sure exactly how oracle foreclose diagonalization - that seems to also be something complexity theorists take by demonstration rather than formally prove.
Anyway, best of luck to them...
Edit: Also, it occurs to me that a lot of the core math curriculum, even at the starting graduate level, has been somewhat "sanitized". All the results have been digested to the point of seeming logical from the start. The "edge" of any field probably would look messier than that.