False belief: "There are no known sub-exponential time algorithms for NP-complete problems."
This one is tricky for a couple of reasons. The first is that the term "sub-exponential" is sometimes defined in different ways. With a sufficiently strong definition of "sub-exponential" the above statement is true, in the sense that there is no known separation of the complexity classes NP and EXPTIME (EXPTIME being the class of languages decidable in time $2^{p(n)}$ where $p(n)$ is a polynomial). However, it is quite common to refer to an $O(2^{\sqrt{n}})$ algorithm as "sub-exponential." It is trivial to construct an NP-complete problem that can be solved in sub-exponential time in this sense, because the standard definition of a reduction allows you to expand the size of the input from $n$ to $n^2$ say (e.g., by padding with zeros). But less artificial examples also exist, such as the planar traveling salesman problem, which was shown by Smith to be solvable in $2^{O(\sqrt{n})}$ time without any artificial padding. What is true is that there are many NP-complete problems, such as 3SAT, for which no subexponential algorithms are known if you do not artificially pad the representation of the instances. (Reducing 3SAT to planar TSP does not work because the instance size blows up during the reduction.)
More crudely,
Often this false belief shows up in the following form: "Factoring cannot be NP-complete because there are untold numbers of people out there who think that "NP" stands subexponential algorithms for factoring." non-polynomial."It is true that factoring is not known to be NP-complete but the reasoning is wrong. Showing that factoring is NP-complete would not automatically yield subexponential algorithms for all other NP-complete problems.
