Exponential time hypothesis

In computational complexity theory, the exponential time hypothesis is an unproven computational hardness assumption that was formulated by . It states that satisfiability of 3-CNF Boolean formulas cannot be solved in subexponential time, i.e., for all constant , where n is the number of variables in the formula. The exponential time hypothesis, if true, would imply that P ≠ NP, but it is a stronger statement. It implies that many computational problems are equivalent in complexity, in the sense that if one of them has a subexponential time algorithm then they all do, and that many known algorithms for these problems have optimal or near-optimal time complexity. The -SAT problem is a version of the Boolean satisfiability problem in which the input to the problem is a Boolean expression in conjunctive normal form (that is, an and of ors of variables and their negations) with at most variables per clause. The goal is to determine whether this expression can be made to be true by some assignment of Boolean values to its variables. 2-SAT has a linear time algorithm, but all known algorithms for larger take exponential time, with the base of the exponential function depending on . For instance, the WalkSAT probabilistic algorithm can solve -SAT in average time where is the number of variables in the given -SAT instance. For each integer , define to be the smallest number such that -SAT can be solved in time . This minimum might not exist, if a sequence of better and better algorithms have correspondingly smaller exponential growth in their time bounds; in that case, define to be the infimum of the real numbers for which -SAT can be solved in time . Because problems with larger cannot be easier, these numbers are ordered as , and because of WalkSAT they are at most The exponential time hypothesis is the conjecture that they are all nonzero, or equivalently, that the smallest of them, , is nonzero. Some sources define the exponential time hypothesis to be the slightly weaker statement that 3-SAT cannot be solved in time .