Question

In P vs NP, there is SUBEXP class as a subset of the EXP class. Do you think there is any relation between EXP and SUBEXP?

Hint: You may want to read up on Exponential Time Hypothesis.

Answer 1

The Exponential Time Hypothesis (ETH) states that 3-SAT is not solvable in subexponential time in the worst-case. In other words, any algorithm that solves the 3-SAT needs at least exponential time. Suppose the ETH is true, then it means that SUBEXP is a strict subset of EXP, that is, there is a decision problem (3-SAT) that is not solvable in subexponential time but is solvable in exponential time (Note that 3-SAT is solvable in exponential time by simply trying out all possible assignments to the variables). Another implication is that if the ETH is true, then P is not equal to NP. This is because the 3-SAT which belongs to NP and is complete for NP has no polynomial-time algorithm (if there is no subexponential time algorithm, it directly implies there is no polynomial-time algorithm).