3 ms·
Exponential time hypothesis implies P!=NP, but converse is not true. It is possible that SAT takes subexponential but superpolynomial time.
by 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 agoAh, a very valid point! This sort of thing is exactly what I love about Computer Science.