Common false beliefs in theoretical computer science EDIT AT 10/12/08:

I'll try to modified the question so it may interest more people to share their opinions. We NEED your contributions!

This post is inspired by the one in MO: Examples of common false beliefs in mathematics. Big lists sometimes generate a massive number of answers the qualities of which are hard to control, but after the success of the related post on MO I am convinced that it would be helpful to list a bunch of common false beliefs in TCS.

Still, since the site is designed for answering research level questions, examples like $\mathsf{NP}$ stands for non-polynomial time should be not on the list. Meanwhile, we do want some examples that may not be hard, but without thinking in details it looks reasonable as well. We want the examples to be educational, and usually appears when studying the subject at the first time.


  What are some (non-trivial) examples of common false beliefs in theoretical computer science, that appear to people who are studying in this area?


To be precise, we want examples different from surprising results and counterintuitive results in TCS; these kinds of results make people hard to believe, but they are TRUE. Here we are asking for surprising examples that people may think it is true at the first glance, but after a deeper thought the fault within is exposed.



As an example of proper answers on the list, this one comes from the field of algorithms and graph-theory:

For an $n$-node graph $G$, a $k$-edge separator $S$ is a subset of edges of size $k$, where the nodes of $G \setminus S$ can be partition into two non-adjacent parts, each consists of at most $3n/4$ nodes. We have the following "lemma":


  A tree has a 1-edge separator.


Right?
This is one is common to computational geometry, but endemic elsewhere: Algorithms for the real RAM can be transferred to the integer RAM (for integer restrictions of the problem) with no loss of efficiency.  A canonical example is the claim “Gaussian elimination runs in $O(n^3)$ time.”  In fact, careless elimination orders can produce integers with exponentially many bits.

Even worse, but still unfortunately common: Algorithms for the real RAM with floor function can be transferred to the integer RAM with no loss of efficiency.  In fact, a real-RAM+floor can solve any problem in PSPACE or in #P in a polynomial number of steps.