3 ms·

Short version: computer scientists have shown that if the Edit Distance problem can be solved in sub-quadratic time, then SAT can be solved in sub-exponential t

by mabbo 11y ago

Short version: computer scientists have shown that if the Edit Distance problem can be solved in sub-quadratic time, then SAT can be solved in sub-exponential time, and therefore P=NP.

sanxiyn 11y ago
Exponential time hypothesis implies P!=NP, but converse is not true. It is possible that SAT takes subexponential but superpolynomial time.
- mabbo 11y ago
  Ah, a very valid point! This sort of thing is exactly what I love about Computer Science.