Common false beliefs in theoretical computer science

Question

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?

Answer 1

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.

Answer 2

I've just got another myth busted, which is contributed by @XXYYXX's answer to this post:

• A problem X is $\mathsf{NP}$-hard if there is a polynomial time (or, logspace) reduction from all $\mathsf{NP}$ problems to X.
• Assume Exponential time hypothesis, 3-SAT does not have a sub-exponential time algorithm. Also, 3-SAT is in $\mathsf{NP}$.
• So no $\mathsf{NP}$-hard problems X have sub-exponential time algorithms. Otherwise a sub-exponential time algorithm for X + a polynomial time reduction = a sub-exponential time algorithm for 3-SAT.

But we do have sub-exponential time algorithms for some NP-hard problems.

Answer 3

A false belief that was popularized this year and is told many times when one tries to explain the whole $P \neq NP$ problem, since $P$ is explained as efficient :

"If $P=NP$ , then we can solve a vast number of problems efficiently. If not, we cannot"

If $3SAT$ can be solved in $O(n^{googolplex})$ then $P=NP$ . I don't think anyone would even think of running this algorithm.

If $P \neq NP$ , we can still have an algorithm for $TSP$ that runs in $n^{\log(\log n)}$ , which is smaller than $n^{5}$ for $n\leq2^{32}$ . Most people would be more than happy to be able to solve $TSP$ for 4 billion cities that fast.

Answer 4

Distributed computing = distributed high-performance computing (clusters, grids, clouds, seti@home, ...).

Distributed algorithms = algorithms for these systems.

---

Spoiler: If this does not sound that much like a "false belief", I suggest that you have a look at conferences such as PODC and DISC, and see what kind of work people are really doing when they study theoretical aspects of distributed computing.

A typical problem setting is the following: We have a cycle with $n$ nodes; the nodes are labelled with unique identifiers from the set $\{1,2,...,\text{poly}(n)\}$; the nodes are deterministic and they exchange messages with each other in a synchronous manner. How many synchronous communication rounds (as a function of $n$) are needed to find a maximal independent set? How many rounds are needed to find an independent set with at least $n/1000$ nodes? [The answer to both of these questions is exactly $\Theta(\log^* n)$, discovered in 1986–2008.]

That is, people often study problems that are completely trivial from the perspective of centralised algorithms, and have very little in common with any kind of supercomputing or high-performance computing. The point certainly is not speeding up centralised computation by using more processors, or anything like that.

The goal is to build a complexity theory by classifying fundamental graph problems according to their computational complexity (e.g., how many synchronous rounds are needed; how many bits are transmitted). Problems like independent sets in cycles may seem pointless, but they serve a role similar to 3-SAT in centralised computing: a very useful starting point in reductions. For concrete real-world applications, it makes more sense to have a look at devices such as routers and switches in communication networks, instead of computers in grids and clusters.

This false belief is not entirely harmless. It actually makes it fairly difficult to sell work related to theory of distributed algorithms to the general TCS audience. I have received hilarious referee reports from TCS conferences...

Answer 5

Here's my two cents:

The complexity class $\mathsf{RL}$, the randomized logspace, is defined as an analog of $\mathsf{RP}$, that is, the decision problems that can be solved by a non-deterministic logspace machine $M$, where

• for a positive instance, $M$ accepts with probability at least $1/2$;
• for a negative instance, $M$ rejects with probability $1$.

Furthermore, the machine always halt.

Is the definition correct? (No)

Answer 6

An elementary one, but common when we first dealing with asymptotic notations. Consider the following "proof" to the recurrence relation $T(n) = 2T(n/2) + O(n \log n)$ and $T(1) = 1$:

We prove by induction. For the base case it holds for $n=1$. Assume the relation holds for all numbers smaller than $n$,

$\begin{align} T(n) &= 2 \cdot T(n/2) + O(n \log n) \\ &= 2 \cdot O(n/2 \log n/2) + O(n \log n) \\ &= O(n \log n/2) + O(n \log n) \\ &= O(n \log n) \\ \end{align}$

Q.E.D. (is it?)