3SAT

3SAT, or the Boolean satisfiability problem, is a problem that asks what is the fastest algorithm to tell for a given formula in Boolean algebra (with unknown number of variables) whether it is satisfiable, that is, whether there is some combination of the (binary) values of the variables that will give 1.

For example, the formula "A+1" is satisfiable because, whether A is 0 or 1, the result is always 1 ("+" here means "binary or", as usual in Boolean algebra). The formula "A * B" is also satisfiable, because the result is one if both A and B are 1. Yet, the formula "A*0" is not satisfiable, because, no matter what A is, the result is always zero.

There are many fast algorithms to solve that; however, each of them runs in exponential time (relative to the formula length) in the worst case. The "exponential time hypothesis" states that this is true even for the best possible algorithm. If that's true, that means that P=NP is incorrect (and proving that hypothesis would get you a big prize); however, even if P=NP is not true, that doesn't mean the exponential time hypothesis is true.

3SAT and Boolean satisfiability problem are actually not complete synonyms. 3SAT asks whether it is possible to solve the Boolean satisfiability problem provided that there are at most 3 variables between each pair of parentheses in the Boolean formula. So, it's a simpler problem, but there is still no algorithm to solve that which is both always correct (not heuristic) and always runs in less than exponential time.