4 ms·
"as far as I know, proving an exponential lower bound for an NP complete problem doesnt immediately rule that P!=NP". that statement is FALSE. P!=NP is exactly
by vznvzn 14y ago
"as far as I know, proving an exponential lower bound for an NP complete problem doesnt immediately rule that P!=NP". that statement is FALSE. P!=NP is exactly a consequence of proving exponential lower time bounds. actually P!=NP would be a consequence of even proving somewhat weaker superpolynomial time bounds on any NP complete problem...
- mdxn 14y agoI was clearly referring to exponential circuit sizes (note the sentence before it), not exponential time. By the way, you can edit your original reply to contain more information rather than just making a bunch of new ones.
- vznvzn 14y agooops. thx for info. didnt notice that. new to this. sorry for multiple replies that should just be edits.