<p>This is one is common to computational geometry, but endemic elsewhere: <strong>Algorithms for the real RAM can be transferred to the integer RAM (for integer restrictions of the problem) with no loss of efficiency.</strong>  A canonical example is the claim “Gaussian elimination runs in $O(n^3)$ time.”  In fact, careless elimination orders can produce integers with <a href="http://portal.acm.org/citation.cfm?id=258740">exponentially many bits</a>.</p>

<p>Even worse, but still unfortunately common: <strong>Algorithms for the real RAM <em>with floor function</em> can be transferred to the integer RAM with no loss of efficiency.</strong>  In fact, a real-RAM+floor can solve <a href="http://www.computational-geometry.org/mailing-lists/compgeom-announce/2003-December/000852.html">any problem in PSPACE or in #P in a polynomial number of steps</a>.</p>

CC BY-SA 3.0
2018-04-25T23:58:06.900Z
"After we did the integer Gaussian elimination, we know how to find a solution."
Albert Hendriks
CC BY-SA 2.5
2010-12-11T08:16:53.347Z
The Gaussian elimination misconception is very wide-spread. Perhaps part of the problem is that we often work on finite fields and, since there is no problem there, we forget.
slimton
CC BY-SA 2.5
2010-12-08T18:18:58.277Z
2010-12-08T18:18:58.277Z
Jeffε
<p>I've just got another myth busted, which is contributed by @XXYYXX's <a href="https://cstheory.stackexchange.com/questions/3620/subexponentially-solvable-hard-graph-problems/3623#3623">answer to this post</a>:</p>

<ul>
<li>A problem X is $\mathsf{NP}$-hard if there is a polynomial time (or, logspace) reduction from all $\mathsf{NP}$ problems to X.</li>
<li>Assume Exponential time hypothesis, 3-SAT does not have a sub-exponential time algorithm. Also, 3-SAT is in $\mathsf{NP}$.</li>
<li>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.</li>
</ul>

<p>But <a href="http://hal.inria.fr/docs/00/47/66/86/PDF/cops_journal_2008_10_16.pdf" rel="noreferrer">we do have</a> sub-exponential time algorithms for some NP-hard problems.</p>

CC BY-SA 2.5
2010-12-07T14:26:41.103Z
I had the same impression.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-12-07T23:07:19.263Z
So what does this tell us about the Exponential Time Hypothesis? Or did I miss some flaw in this line of reasoning?
Mikhail Glushenkov
CC BY-SA 2.5
2010-12-08T00:07:29.383Z
There is a fault in point 3. That is exactly what I've misunderstood for a long time :)
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-08T02:58:29.657Z
I am not sure if I cannot find the fault. Is it that since $P \neq NP$ , the reduction must not be necessarily polynomial but that it can be exponential in time , since both problems would be in EXPTIME (due to ETH?)
chazisop
CC BY-SA 2.5
2010-12-08T04:05:33.490Z
Polynomial-time reductions can change the input size by a polynomial amount.  So if you reduce an instance of Q of size n to an instance of P of size n squared, a 2 to the root n algorithm for P only gives you a 2 to the n algorithm for Q.
Russell Impagliazzo
CC BY-SA 2.5
2010-12-07T14:14:03.173Z
2010-12-11T08:21:16.887Z
2017-04-13T12:32:30.623Z
Hsien-Chih Chang 張顯之
<p>This is really a false belief in math, but comes up often in TCS contexts: If random variables $X$ and $Y$ are independent, then conditioned on $Z$ they remain independent. (false even if $Z$ is independent of both $X$ and $Y$.)</p>

CC BY-SA 3.0
2013-05-02T21:22:53.767Z
Do you have a favorite simple example of this you would recommend, to help people quickly recognize why it is false?
D.W.
CC BY-SA 3.0
2013-05-03T21:31:24.270Z
Say $X$ and $Y$ are independent and uniformly random bits, and $Z = X+Y$ (mod 2). Then, $Z$ is independent of $X$ and is independent of $Y$, but conditioned on $Z$, knowing $X$ reveals $Y$ and vice versa.
Mahdi Cheraghchi
CC BY-SA 3.0
2013-01-24T04:30:47.437Z
2013-01-24T04:30:47.437Z
Mahdi Cheraghchi
<p>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 : </p>

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

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

<p>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.</p>

CC BY-SA 3.0
2013-01-22T15:57:44.663Z
“For every polynomial-time algorithm you have, there is an exponential algorithm that I would rather run” -- Alan Perlis, via [Gödel’s Lost Letter and P=NP](http://rjlipton.wordpress.com/2009/02/13/polynomial-vs-exponential-time/).
John K.
CC BY-SA 2.5
2010-12-08T02:02:21.367Z
The blog post by Lipton are nice: http://rjlipton.wordpress.com/2009/07/03/is-pnp-an-ill-posed-problem
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-08T01:56:09.777Z
2010-12-08T02:00:17.717Z
2010-12-08T02:00:17.717Z
chazisop
<p>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$:</p>

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

<p>$\begin{align}
T(n) &amp;= 2 \cdot T(n/2) + O(n \log n) \\
&amp;= 2 \cdot O(n/2 \log n/2) + O(n \log n) \\
&amp;= O(n \log n/2) + O(n \log n) \\
&amp;= O(n \log n) \\
\end{align}$
</p>

<p>Q.E.D. (is it?)</p>

CC BY-SA 2.5
2010-12-08T14:35:17.507Z
I've seen students do this. This is one of the pitfalls of abusing notation and writing $f(x) = O(g(x))$ rather than $f(x) \in O(g(x))$.
Aaron Roth
CC BY-SA 3.0
2013-05-18T09:04:53.023Z
I've seen researchers in theoretical computer science do variants of this error too ;)
J.y B.y
CC BY-SA 2.5
2010-12-08T02:19:32.887Z
2010-12-08T02:19:32.887Z
Hsien-Chih Chang 張顯之
<p>Distributed computing = distributed high-performance computing (clusters, grids, clouds, seti@home, ...).</p>

<p>Distributed algorithms = algorithms for these systems.</p>

<hr>

<p><strong>Spoiler:</strong> 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.</p>

<p>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.]</p>

<p>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.</p>

<p>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.</p>

<p>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...</p>

CC BY-SA 2.5
2010-12-08T01:10:50.080Z
Concerning computing, I wouldn't say this is not a false belief, but rather an outdated one. Other than multicore processors, small-scale distributed computing was a trivial case of the high-performance one (from what I know at least). With cores being "computers" but in such a small distance, with no network between them , new problems arise. I agree however that distributed algorithms should be used for m >= 2 nodes.
chazisop
CC BY-SA 3.0
2013-01-24T13:56:44.597Z
So you are just saying that people confuse parallel computing with distributed computing?
Sasho Nikolov
CC BY-SA 3.0
2013-05-03T06:59:29.017Z
I think your claim does not apply to theoretical computer scientists, though it may apply to pratictioners without a theoretical background. As pointed out by Sasho Nikolov, people working in the field know very well the differences between parallel and distributed computing. The problem arising in clusters, grids, clouds etc strictly depend on the context. For instance, we do not assume failures when using a cluster or a cloud, but we do for grids. And so on.
Massimo Cafaro
CC BY-SA 3.0
2013-05-03T07:02:17.077Z
Moreover, for this scientific community, distributed algorithms are algorithms for problems such as those commonly found in the books of Nancy Lynch, Hagit Attiya and Jennifer Welch, and Gerard Tel to name a few. And, as such, these algorithms are designed for a specific theoretical distributed computing model, and analyzed as required in terms of the resources used (time complexity, message complexity, bit complexity, number of rounds etc).
Massimo Cafaro
CC BY-SA 3.0
2013-05-03T08:56:16.660Z
@MassimoCafaro: Of course people who work in the field of distributed computing know what is distributed computing. However, my experience is that *theoretical computer scientists* in general do not know what is distributed computing.
Jukka Suomela
CC BY-SA 2.5
2010-12-07T13:56:27.713Z
2010-12-08T11:10:05.650Z
2010-12-08T11:10:05.650Z
Jukka Suomela
<p>Until recently I thought that every multi-tape Turing machine $M$ that runs in time $T(n)$ can be simulated by a two-tape oblivious Turing machinne $M_o$ in time $O(T(n)\log T(n))$ in the following sense: </p>

<ul>
<li>the movement of $M_o$'s heads depends only on the input length</li>
<li>for all inputs of the same length, $M_o$ stops at the same time (which is $\Theta(T(n)\log T(n))$).</li>
</ul>

<p>(see <a href="http://rjlipton.wordpress.com/2009/07/28/oblivious-turing-machines-and-a-crock/" rel="nofollow noreferrer">this post</a> of rjlipton for example)</p>

<p>Well, the second line does not hold in general, if $EXP-TIME\neq NEXP-TIME$. We need a fully time-constructible function of order $\Theta(T(n)\log T(n))$ (see <a href="https://cstheory.stackexchange.com/questions/15019/equivalent-definitions-of-time-constructibility">this</a> question for the definition of (fully) time-constructible functions) or we need to allow $M_o$ to run for infinite time (we allow $M_o$ to run after it reaches the accept state in $O(T(n)\log T(n))$ time). The problem is, that for general time-constructible $T:\mathbb{N}\rightarrow\mathbb{N}$ we are unable to "measure" $\Theta(T(n)\log T(n))$ steps in time $O(T(n)\log T(n))$ unless $EXP-TIME=NEXP-TIME$. </p>

<p>The proof of this claim is very similar to the proof in the answer of Q1 <a href="https://cstheory.stackexchange.com/questions/15019/equivalent-definitions-of-time-constructibility/16085#16085">here</a>, thus we will only give the key ideas.</p>

<p>Take an arbitrary problem $L\in NEXP-TIME$, $L\subseteq\{0,1\}^*$. Then there exists a $k\in\mathbb{N}$, s.t. $L$ can be solved by a NDTM $M$ in $2^{n^k}$ steps. We can assume that at each step $M$ goes in at most two different states for simplicity. Next define the function
$$f(n)=\left\{\begin{array}{ll}
  (8n+2)^2  &amp; \mbox{if }\left(\mbox{first } \lfloor\sqrt[k]{\lfloor\log n\rfloor+1}\rfloor\mbox{ bits of } bin(n)\right)\in L\\
  8n+1 &amp; \mbox{else}
 \end{array}
\right.$$
It can be proven that $f$ is time-construcible.</p>

<p>Now suppose that some oblivious Turing machine runs in time $g(n)=\Theta(f(n)\log f(n))$. Then $g$ is fully time-constructible. </p>

<p>Now the following algorithm solves $L$:</p>

<ul>
<li>on input $x$, let $n$ be the number with binary representation $x00\ldots 0$ ($|x|^{k-1}$ zeros). It follows that $x=\left(\textrm{first }\lfloor\sqrt[k]{\lfloor\log n\rfloor+1}\rfloor\textrm{ bits of }bin(n)\right)$.</li>
<li>compute $g(n)$ in time $g(n)$. If $g(n)$ is large enough, then $x\in L$, else $x\not\in L$. (this only works for large enough $n$. How large depends on $g$.)</li>
</ul>

<p>This algorithm runs in exponential time and solves $L$. Since $L\in NEXP-TIME$ was arbitrary, $EXP-TIME=NEXP-TIME$. </p>

CC BY-SA 3.0
2013-01-14T20:31:35.883Z
2013-01-14T20:36:51.217Z
2017-04-13T12:32:30.623Z
David G
<p>Here's my two cents:</p>

<p>The complexity class $\mathsf{RL}$, the <strong>randomized logspace</strong>, 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</p>

<ul>
<li>for a positive instance, $M$ accepts with probability at least $1/2$;</li>
<li>for a negative instance, $M$ rejects with probability $1$.</li>
</ul>

<p>Furthermore, the machine always halt.</p>

<p>Is the definition correct? (No)</p>

CC BY-SA 4.0
2020-01-05T15:25:14.220Z
Hint: Is RL defined by this definition obviously contained in RP?
Lwins
CC BY-SA 2.5
2010-12-07T10:47:53.243Z
2010-12-07T10:47:53.243Z
Hsien-Chih Chang 張顯之
<p>Let $f$ and $g$ be fully time-constructible functions (i.e. there exists a DTM that on input $1^n$ makes exactly $f(n)$ (resp. $g(n)$) steps) and let $f(n+1)=o(g(n))$.</p>

<p><strong>The nondeterministic time-hierarchy</strong> is many times <strong>(superficially)</strong> stated as $NTIME(f(n))\subsetneq NTIME(g(n))$. (proof: ask Google for nondeterministic time hierarchy).</p>

<p>Well, the hierarchy actualy gives only $NTIME(g(n)) - NTIME(f(n))\neq\emptyset$. We would need e.g. $f(n)\leq g(n)$ for $NTIME(f(n))\subsetneq NTIME(g(n))$. For functions $f,g$ such that $f(n+1)=o(g(n))$, $f(n)\leq g(n)$ is very common. But strictly speaking, nondeterministic time hierarchy is many times stated superficially.</p>

<p>To show that $NTIME(f(n))\subseteq NTIME(g(n))$ does not hold for all fully time-constructible $f,g$ s.t. $f(n+1)=o(g(n))$, define $$f(n)=\left\{\begin{array}{ll}
  n+1  &amp; n \mbox{ odd}\\
  (n+1)^3 &amp; \mbox{else}
 \end{array}
\right.$$
and $g(n)=f(n+1)^2$. It is easy to see that $f$ and $g$ are fully time constructible and $f(n+1)=o(g(n))$. From nondeterministic time hierarchy we know that there is some language $L\in NTIME((n+1)^3)-NTIME((n+1)^2)$ over $\{0,1\}$. Define
$$L_1=\{0x_10x_2\ldots 0x_n;\ \ x_1x_2\ldots x_n\in L\}.$$</p>

<p>It follows that $L_1\in NTIME(f(n))$. It is easy to see that from $L_1\in NTIME(g(n))$ follows $L\in NTIME((n+1)^2)$, which is not true. Hence, $L_1\in NTIME(f(n))-NTIME(g(n))$.</p>

CC BY-SA 3.0
2013-01-21T22:38:23.440Z
2013-05-02T20:28:58.587Z
2013-05-02T20:28:58.587Z
David G
<p>I've frequently heard it stated that Valiant-Vazirani says that $\mathsf{NP}$ randomly reduces to $\mathsf{UP}$, or that $\mathsf{NP} \subseteq \mathsf{RP}^{\mathsf{UP}}$, or that $\mathsf{NP} \subseteq \mathsf{R} \cdot \mathsf{UP}$. In particular, this would imply that if Valiant-Vazirani could be derandomized, then $\mathsf{NP}=\mathsf{UP}$. But in fact Valiant-Vazirani says that $\mathsf{NP} \subseteq \mathsf{RP}^{\mathsf{PromiseUP}}$.</p>

<p>Closely related false belief: $\mathsf{UP}$ is the class of languages $L$ with a nondeterministic poly time verifier such that $x \in L$ iff there is a unique witness. The correction is that the verifier must satisfy the semantic property that on <em>all</em> instances, there is at most one witness. The definition above, without the correction, is the definition of $\mathsf{US}$. But $\mathsf{US}$ is <em>very</em> different from $\mathsf{UP}$: for example, $\mathsf{coNP} \subseteq \mathsf{US}$.</p>

CC BY-SA 3.0
2017-08-02T08:32:13.877Z
what does 'the semantic property that on all instances' mean?
Turbo
CC BY-SA 3.0
2017-08-02T14:20:43.107Z
@777: semantic property means: cannot be verified directly from the structure (aka syntax) of the TM / algorithm itself. The phrase makes more sense if you continue it past the comma, i.e.: the property that: "on all instances there is at most one witness"
Joshua Grochow
CC BY-SA 4.0
2019-12-19T05:32:02.320Z
@JoshuaGrochow p =up implies NP is RP?
VS.
CC BY-SA 4.0
2019-12-19T06:40:29.093Z
@VS.: I don't think so. PromiseUP = PromiseP implies NP=RP. The difference is part of the point of this answer...
Joshua Grochow
CC BY-SA 4.0
2019-12-19T08:50:20.260Z
@JoshuaGrochow sorry but doesn't unambiguous sat belong to UP ( https://en.m.wikipedia.org/wiki/Valiant–Vazirani_theorem)? So if p is up then usat is in p. No?
VS.
CC BY-SA 4.0
2019-12-19T16:23:37.700Z
@VS.: No. This is precisely the point. UnambiguousSAT is in PromiseUP, and it is possible for P=UP but for PromiseUP to still be separate. (Moreover, deciding whether an input satisfies the promise - that is, whether $\phi$ has *at most* 1 satisfying assignment, is coNP-complete.)
Joshua Grochow
CC BY-SA 4.0
2021-04-27T23:38:11.983Z
@JoshuaGrochow would $PP=ZPP$ imply $ NP\subseteq promiseUP^{NP}\subseteq promiseP^{ZPP}\subseteq promiseUP\subseteq UP^{zpp}\subseteq UP\subseteq ZPP$. In other words $PP=ZPP\iff PP=PromiseUP=UP=NP=ZPP$?
User2021
CC BY-SA 4.0
2021-11-02T05:20:14.657Z
@JoshuaGrochow Is it possible PromiseUL=PromiseL implies NL=RLP? It appears RP = P implies NP in PromiseUP correct? So if RLP=L would NL in PromiseUL hold? There seems to be an overall connection. It is believed NL is UL which is in PromiseUL.
Turbo
CC BY-SA 4.0
2021-11-02T05:29:47.547Z
@Mr.: I do not believe that is correct, actually. RP=P does not tell you (at least not obviously) anything about their relativized versions $\mathsf{P}^{\mathsf{PromiseUP}}, \mathsf{RP}^{\mathsf{PromiseUP}}$
Joshua Grochow
CC BY-SA 4.0
2021-11-02T05:34:48.483Z
Thank you.......
Turbo
CC BY-SA 4.0
2023-05-18T03:42:28.180Z
@JoshuaGrochow given an NP problem, can we using Cook Levin convert parsimoniously to 3sat and from there many one reduce to 0/1 permanent. If the permanent is 0 there is no solution. Can't we identify this using perfect matching algorithms? I know I am making a silly mistake but what it is I don't know.
Turbo
CC BY-SA 4.0
2023-05-18T23:48:34.323Z
@JoshuaGrochow I think I understand. Only the first step in Valiant's reduction of #3SAT to integer permanent is parsimonious and permanent value is 4^t #phi. The conversion to 0/1 permanent is many one and the value is more complicated.
Turbo
CC BY-SA 4.0
2023-05-19T16:24:48.713Z
Yes. Slightly simplified by Zanko https://doi.org/10.1142/S0129054191000066, but still works modulo a large number, so still not parsimonious. (Advantage of Zanko's construction: just modulo just a single number, and the number doesn't need to be prime. In contrast to Valiant's original construction which uses many primes.)
Joshua Grochow
CC BY-SA 3.0
2013-05-03T15:04:39.593Z
2013-05-03T15:04:39.593Z
Joshua Grochow
<p><strong>Superpolynomial time complexity cannot be in P.</strong> While this appears easy to believe, it is actually a false belief.</p>
<p>Formally, we may think that if <span class="math-container">$f(n)$</span> is a superpolynomial function, then <span class="math-container">${\mathsf {DTIME}}(f(n)) \not\subseteq {\mathsf P}$</span>.  Surprisingly, this is wrong. In fact there exists a superpolynomial function <span class="math-container">$f(n)$</span> with
<span class="math-container">$${\mathsf P} = {\mathsf {DTIME}}(f(n)). $$</span>
See the answer to the question
<a href="https://cstheory.stackexchange.com/questions/25794/is-p-equal-to-the-intersection-of-all-superpolynomial-time-classes">Is P equal to the intersection of all superpolynomial time classes?</a></p>

CC BY-SA 4.0
2021-09-28T05:48:22.347Z
I think the first sentence is imprecise. P = DTIME(f(n)) for some superpolynomial f is not the same as saying there exists L in P with superpolynomial time complexity.
usul
CC BY-SA 4.0
2021-09-28T15:52:23.480Z
@usul Yes, you are right. By "superpolynomial time complexity" I wanted to refer to the class DTIME(f(n)) with a superpolynomial function f(n), rather than to a single language, as explained in the second paragraph.
Andras Farago
CC BY-SA 4.0
2021-09-28T03:28:18.977Z
2021-09-28T03:28:18.977Z
Andras Farago
<p>&quot;When a problem is algorithmically undecidable, it means that it has a definite provable answer (yes or no) on all instances, but no unique algorithm is capable to reach this answer uniformly on all instances.&quot;</p>
<p>It was a revelation for me to discover that any undecidable problem has particular instances that are independent of ZFC. Otherwise, exhaustively searching for proofs of yes or no would yield an algorithm.</p>

CC BY-SA 4.0
2021-09-27T18:52:27.437Z
2021-09-27T18:52:27.437Z
Denis
<p>If $\mu$ is the expected value of $X$, we expect that $\{X=\mu\}$ will actually happen.</p>

CC BY-SA 3.0
2013-05-17T15:16:37.183Z
This is certainly a common false belief among _students_ of theoretical computer science, but it's not so common among theoretical computer science _researchers_.
Jeffε
CC BY-SA 3.0
2013-05-17T13:10:02.387Z
2013-05-17T13:10:02.387Z
user1596990
<p>This post is inspired by the one in MO: <a href="https://mathoverflow.net/questions/23478/examples-of-common-false-beliefs-in-mathematics">Examples of common false beliefs in mathematics</a>.</p>
<p>Since the site is designed for answering research level questions, examples like <em><span class="math-container">$\mathsf{NP}$</span> stands for non-polynomial time</em> 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 for the first time.</p>
<blockquote>
<p>What are some (non-trivial) examples of common false beliefs in theoretical computer science, that appear to people who are studying in this area?</p>
</blockquote>
<p>To be precise, we want examples different from <a href="https://cstheory.stackexchange.com/questions/276/surprising-results-in-complexity-not-on-the-complexity-blog-list">surprising results</a> and <a href="https://cstheory.stackexchange.com/questions/2802/are-there-any-counterintuitive-results-in-theoretical-computer-science">counterintuitive results</a> in TCS; these kinds of results are surprising to many people, but they are TRUE. Here we are asking for surprising examples that people may think are true at first glance, but after deeper thought the fault within is exposed.</p>
<hr />
<p>As an example of proper answers on the list, this one comes from the field of algorithms and graph-theory:</p>
<p>For an <span class="math-container">$n$</span>-node graph <span class="math-container">$G$</span>, a <span class="math-container">$k$</span>-edge separator <span class="math-container">$S$</span> is a subset of edges of size <span class="math-container">$k$</span>, where the nodes of <span class="math-container">$G \setminus S$</span> can be partition into two non-adjacent parts, each consists of at most <span class="math-container">$3n/4$</span> nodes. We have the following &quot;lemma&quot;:</p>
<blockquote>
<p>A tree has a 1-edge separator.</p>
</blockquote>
<p>Right?</p>

CC BY-SA 4.0
2021-09-28T14:04:45.577Z
(Since it took me a few moments, the 'easy' counterexample: consider the star tree, with edges between node 0 and each of nodes $1\ldots n$. OTOH, for _binary_ trees...)
Steven Stadnicki
<big-list><examples>
Common false beliefs in theoretical computer science
Hsien-Chih Chang 張顯之
# Common false beliefs in theoretical computer science

(Asked by: username_0 on 2010-12-07)

This post is inspired by the one in MO: [Examples of common false beliefs in mathematics](https://mathoverflow.net/questions/23478/examples-of-common-false-beliefs-in-mathematics).

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 for 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](https://cstheory.stackexchange.com/questions/276/surprising-results-in-complexity-not-on-the-complexity-blog-list) and [counterintuitive results](https://cstheory.stackexchange.com/questions/2802/are-there-any-counterintuitive-results-in-theoretical-computer-science) in TCS; these kinds of results are surprising to many people, but they are TRUE. Here we are asking for surprising examples that people may think are true at first glance, but after 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?

**Tags:** big-list, examples
> **Comments:**
> **username_1**: (Since it took me a few moments, the 'easy' counterexample: consider the star tree, with edges between node 0 and each of nodes $1\ldots n$. OTOH, for _binary_ trees...)  

---

## 13 answers

### Answer by username_2 on 2010-12-08. Score: 67

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](http://portal.acm.org/citation.cfm?id=258740).

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](http://www.computational-geometry.org/mailing-lists/compgeom-announce/2003-December/000852.html).

> **Comments:**
> **username_4**: The Gaussian elimination misconception is very wide-spread. Perhaps part of the problem is that we often work on finite fields and, since there is no problem there, we forget.  
> **username_3**: "After we did the integer Gaussian elimination, we know how to find a solution."  

---

### Answer by username_0 on 2010-12-07. Score: 47

I've just got another myth busted, which is contributed by @XXYYXX's [answer to this post](https://cstheory.stackexchange.com/questions/3620/subexponentially-solvable-hard-graph-problems/3623#3623):

* 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](http://hal.inria.fr/docs/00/47/66/86/PDF/cops_journal_2008_10_16.pdf) sub-exponential time algorithms for some NP-hard problems.

> **Comments:**
> **username_5**: I had the same impression.  
> **username_6**: So what does this tell us about the Exponential Time Hypothesis? Or did I miss some flaw in this line of reasoning?  
> **username_0**: There is a fault in point 3. That is exactly what I've misunderstood for a long time :)  
> **username_7**: I am not sure if I cannot find the fault. Is it that since $P \neq NP$ , the reduction must not be necessarily polynomial but that it can be exponential in time , since both problems would be in EXPTIME (due to ETH?)  
> **username_8**: Polynomial-time reductions can change the input size by a polynomial amount.  So if you reduce an instance of Q of size n to an instance of P of size n squared, a 2 to the root n algorithm for P only gives you a 2 to the n algorithm for Q.  

---

### Answer by username_9 on 2013-01-24. Score: 33

This is really a false belief in math, but comes up often in TCS contexts: If random variables $X$ and $Y$ are independent, then conditioned on $Z$ they remain independent. (false even if $Z$ is independent of both $X$ and $Y$.)

> **Comments:**
> **username_10**: Do you have a favorite simple example of this you would recommend, to help people quickly recognize why it is false?  
> **username_9**: Say $X$ and $Y$ are independent and uniformly random bits, and $Z = X+Y$ (mod 2). Then, $Z$ is independent of $X$ and is independent of $Y$, but conditioned on $Z$, knowing $X$ reveals $Y$ and vice versa.  

---

### Answer by username_7 on 2010-12-08. Score: 32

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.

> **Comments:**
> **username_0**: The blog post by Lipton are nice: http://rjlipton.wordpress.com/2009/07/03/is-pnp-an-ill-posed-problem  
> **username_11**: “For every polynomial-time algorithm you have, there is an exponential algorithm that I would rather run” -- Alan Perlis, via [Gödel’s Lost Letter and P=NP](http://rjlipton.wordpress.com/2009/02/13/polynomial-vs-exponential-time/).  

---

### Answer by username_14 on 2010-12-07. Score: 24

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...

> **Comments:**
> **username_7**: Concerning computing, I wouldn't say this is not a false belief, but rather an outdated one. Other than multicore processors, small-scale distributed computing was a trivial case of the high-performance one (from what I know at least). With cores being "computers" but in such a small distance, with no network between them , new problems arise. I agree however that distributed algorithms should be used for m >= 2 nodes.  
> **username_15**: So you are just saying that people confuse parallel computing with distributed computing?  
> **username_16**: I think your claim does not apply to theoretical computer scientists, though it may apply to pratictioners without a theoretical background. As pointed out by Sasho Nikolov, people working in the field know very well the differences between parallel and distributed computing. The problem arising in clusters, grids, clouds etc strictly depend on the context. For instance, we do not assume failures when using a cluster or a cloud, but we do for grids. And so on.  
> **username_16**: Moreover, for this scientific community, distributed algorithms are algorithms for problems such as those commonly found in the books of Nancy Lynch, Hagit Attiya and Jennifer Welch, and Gerard Tel to name a few. And, as such, these algorithms are designed for a specific theoretical distributed computing model, and analyzed as required in terms of the resources used (time complexity, message complexity, bit complexity, number of rounds etc).  
> **username_14**: @MassimoCafaro: Of course people who work in the field of distributed computing know what is distributed computing. However, my experience is that *theoretical computer scientists* in general do not know what is distributed computing.  

---

### Answer by username_0 on 2010-12-08. Score: 22

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?)

> **Comments:**
> **username_12**: I've seen students do this. This is one of the pitfalls of abusing notation and writing $f(x) = O(g(x))$ rather than $f(x) \in O(g(x))$.  
> **username_13**: I've seen researchers in theoretical computer science do variants of this error too ;)  

---

### Answer by username_17 on 2013-01-14. Score: 14

Until recently I thought that every multi-tape Turing machine $M$ that runs in time $T(n)$ can be simulated by a two-tape oblivious Turing machinne $M\_o$ in time $O(T(n)\log T(n))$ in the following sense:

* the movement of $M\_o$'s heads depends only on the input length
* for all inputs of the same length, $M\_o$ stops at the same time (which is $\Theta(T(n)\log T(n))$).

(see [this post](http://rjlipton.wordpress.com/2009/07/28/oblivious-turing-machines-and-a-crock/) of rjlipton for example)

Well, the second line does not hold in general, if $EXP-TIME\neq NEXP-TIME$. We need a fully time-constructible function of order $\Theta(T(n)\log T(n))$ (see [this](https://cstheory.stackexchange.com/questions/15019/equivalent-definitions-of-time-constructibility) question for the definition of (fully) time-constructible functions) or we need to allow $M\_o$ to run for infinite time (we allow $M\_o$ to run after it reaches the accept state in $O(T(n)\log T(n))$ time). The problem is, that for general time-constructible $T:\mathbb{N}\rightarrow\mathbb{N}$ we are unable to "measure" $\Theta(T(n)\log T(n))$ steps in time $O(T(n)\log T(n))$ unless $EXP-TIME=NEXP-TIME$.

The proof of this claim is very similar to the proof in the answer of Q1 [here](https://cstheory.stackexchange.com/questions/15019/equivalent-definitions-of-time-constructibility/16085#16085), thus we will only give the key ideas.

Take an arbitrary problem $L\in NEXP-TIME$, $L\subseteq\{0,1\}^\*$. Then there exists a $k\in\mathbb{N}$, s.t. $L$ can be solved by a NDTM $M$ in $2^{n^k}$ steps. We can assume that at each step $M$ goes in at most two different states for simplicity. Next define the function
$$f(n)=\left\{\begin{array}{ll}
(8n+2)^2 & \mbox{if }\left(\mbox{first } \lfloor\sqrt[k]{\lfloor\log n\rfloor+1}\rfloor\mbox{ bits of } bin(n)\right)\in L\\
8n+1 & \mbox{else}
\end{array}
\right.$$
It can be proven that $f$ is time-construcible.

Now suppose that some oblivious Turing machine runs in time $g(n)=\Theta(f(n)\log f(n))$. Then $g$ is fully time-constructible.

Now the following algorithm solves $L$:

* on input $x$, let $n$ be the number with binary representation $x00\ldots 0$ ($|x|^{k-1}$ zeros). It follows that $x=\left(\textrm{first }\lfloor\sqrt[k]{\lfloor\log n\rfloor+1}\rfloor\textrm{ bits of }bin(n)\right)$.
* compute $g(n)$ in time $g(n)$. If $g(n)$ is large enough, then $x\in L$, else $x\not\in L$. (this only works for large enough $n$. How large depends on $g$.)

This algorithm runs in exponential time and solves $L$. Since $L\in NEXP-TIME$ was arbitrary, $EXP-TIME=NEXP-TIME$.


---

### Answer by username_0 on 2010-12-07. Score: 12

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)

> **Comments:**
> **username_18**: Hint: Is RL defined by this definition obviously contained in RP?  

---

### Answer by username_17 on 2013-01-21. Score: 10

Let $f$ and $g$ be fully time-constructible functions (i.e. there exists a DTM that on input $1^n$ makes exactly $f(n)$ (resp. $g(n)$) steps) and let $f(n+1)=o(g(n))$.

**The nondeterministic time-hierarchy** is many times **(superficially)** stated as $NTIME(f(n))\subsetneq NTIME(g(n))$. (proof: ask Google for nondeterministic time hierarchy).

Well, the hierarchy actualy gives only $NTIME(g(n)) - NTIME(f(n))\neq\emptyset$. We would need e.g. $f(n)\leq g(n)$ for $NTIME(f(n))\subsetneq NTIME(g(n))$. For functions $f,g$ such that $f(n+1)=o(g(n))$, $f(n)\leq g(n)$ is very common. But strictly speaking, nondeterministic time hierarchy is many times stated superficially.

To show that $NTIME(f(n))\subseteq NTIME(g(n))$ does not hold for all fully time-constructible $f,g$ s.t. $f(n+1)=o(g(n))$, define $$f(n)=\left\{\begin{array}{ll}
n+1 & n \mbox{ odd}\\
(n+1)^3 & \mbox{else}
\end{array}
\right.$$
and $g(n)=f(n+1)^2$. It is easy to see that $f$ and $g$ are fully time constructible and $f(n+1)=o(g(n))$. From nondeterministic time hierarchy we know that there is some language $L\in NTIME((n+1)^3)-NTIME((n+1)^2)$ over $\{0,1\}$. Define
$$L\_1=\{0x\_10x\_2\ldots 0x\_n;\ \ x\_1x\_2\ldots x\_n\in L\}.$$

It follows that $L\_1\in NTIME(f(n))$. It is easy to see that from $L\_1\in NTIME(g(n))$ follows $L\in NTIME((n+1)^2)$, which is not true. Hence, $L\_1\in NTIME(f(n))-NTIME(g(n))$.


---

### Answer by username_19 on 2013-05-03. Score: 9

I've frequently heard it stated that Valiant-Vazirani says that $\mathsf{NP}$ randomly reduces to $\mathsf{UP}$, or that $\mathsf{NP} \subseteq \mathsf{RP}^{\mathsf{UP}}$, or that $\mathsf{NP} \subseteq \mathsf{R} \cdot \mathsf{UP}$. In particular, this would imply that if Valiant-Vazirani could be derandomized, then $\mathsf{NP}=\mathsf{UP}$. But in fact Valiant-Vazirani says that $\mathsf{NP} \subseteq \mathsf{RP}^{\mathsf{PromiseUP}}$.

Closely related false belief: $\mathsf{UP}$ is the class of languages $L$ with a nondeterministic poly time verifier such that $x \in L$ iff there is a unique witness. The correction is that the verifier must satisfy the semantic property that on *all* instances, there is at most one witness. The definition above, without the correction, is the definition of $\mathsf{US}$. But $\mathsf{US}$ is *very* different from $\mathsf{UP}$: for example, $\mathsf{coNP} \subseteq \mathsf{US}$.

> **Comments:**
> **username_20**: what does 'the semantic property that on all instances' mean?  
> **username_19**: @777: semantic property means: cannot be verified directly from the structure (aka syntax) of the TM / algorithm itself. The phrase makes more sense if you continue it past the comma, i.e.: the property that: "on all instances there is at most one witness"  
> **username_21**: @JoshuaGrochow p =up implies NP is RP?  
> **username_19**: @VS.: I don't think so. PromiseUP = PromiseP implies NP=RP. The difference is part of the point of this answer...  
> **username_21**: @JoshuaGrochow sorry but doesn't unambiguous sat belong to UP ( https://en.m.wikipedia.org/wiki/Valiant–Vazirani_theorem)? So if p is up then usat is in p. No?  
> **username_19**: @VS.: No. This is precisely the point. UnambiguousSAT is in PromiseUP, and it is possible for P=UP but for PromiseUP to still be separate. (Moreover, deciding whether an input satisfies the promise - that is, whether $\phi$ has *at most* 1 satisfying assignment, is coNP-complete.)  
> **username_22**: @JoshuaGrochow would $PP=ZPP$ imply $ NP\subseteq promiseUP^{NP}\subseteq promiseP^{ZPP}\subseteq promiseUP\subseteq UP^{zpp}\subseteq UP\subseteq ZPP$. In other words $PP=ZPP\iff PP=PromiseUP=UP=NP=ZPP$?  
> **username_20**: @JoshuaGrochow Is it possible PromiseUL=PromiseL implies NL=RLP? It appears RP = P implies NP in PromiseUP correct? So if RLP=L would NL in PromiseUL hold? There seems to be an overall connection. It is believed NL is UL which is in PromiseUL.  
> **username_19**: @Mr.: I do not believe that is correct, actually. RP=P does not tell you (at least not obviously) anything about their relativized versions $\mathsf{P}^{\mathsf{PromiseUP}}, \mathsf{RP}^{\mathsf{PromiseUP}}$  
> **username_20**: Thank you.......  
> **username_20**: @JoshuaGrochow given an NP problem, can we using Cook Levin convert parsimoniously to 3sat and from there many one reduce to 0/1 permanent. If the permanent is 0 there is no solution. Can't we identify this using perfect matching algorithms? I know I am making a silly mistake but what it is I don't know.  
> **username_20**: @JoshuaGrochow I think I understand. Only the first step in Valiant's reduction of #3SAT to integer permanent is parsimonious and permanent value is 4^t #phi. The conversion to 0/1 permanent is many one and the value is more complicated.  
> **username_19**: Yes. Slightly simplified by Zanko https://doi.org/10.1142/S0129054191000066, but still works modulo a large number, so still not parsimonious. (Advantage of Zanko's construction: just modulo just a single number, and the number doesn't need to be prime. In contrast to Valiant's original construction which uses many primes.)  

---

### Answer by username_23 on 2021-09-28. Score: 7

**Superpolynomial time complexity cannot be in P.** While this appears easy to believe, it is actually a false belief.

Formally, we may think that if $f(n)$ is a superpolynomial function, then ${\mathsf {DTIME}}(f(n)) \not\subseteq {\mathsf P}$. Surprisingly, this is wrong. In fact there exists a superpolynomial function $f(n)$ with
$${\mathsf P} = {\mathsf {DTIME}}(f(n)). $$
See the answer to the question
[Is P equal to the intersection of all superpolynomial time classes?](https://cstheory.stackexchange.com/questions/25794/is-p-equal-to-the-intersection-of-all-superpolynomial-time-classes)

> **Comments:**
> **username_24**: I think the first sentence is imprecise. P = DTIME(f(n)) for some superpolynomial f is not the same as saying there exists L in P with superpolynomial time complexity.  
> **username_23**: @usul Yes, you are right. By "superpolynomial time complexity" I wanted to refer to the class DTIME(f(n)) with a superpolynomial function f(n), rather than to a single language, as explained in the second paragraph.  

---

### Answer by username_25 on 2021-09-27. Score: 5

"When a problem is algorithmically undecidable, it means that it has a definite provable answer (yes or no) on all instances, but no unique algorithm is capable to reach this answer uniformly on all instances."

It was a revelation for me to discover that any undecidable problem has particular instances that are independent of ZFC. Otherwise, exhaustively searching for proofs of yes or no would yield an algorithm.


---

### Answer by username_26 on 2013-05-17. Score: -2

If $\mu$ is the expected value of $X$, we expect that $\{X=\mu\}$ will actually happen.

> **Comments:**
> **username_2**: This is certainly a common false belief among _students_ of theoretical computer science, but it's not so common among theoretical computer science _researchers_.  

---

