3
$\begingroup$

The textbook The Nature of Computation uses the following definition of quasipolynomial time:

A quasipolynomial is a function of the form $f(n) = 2^{\Theta(\log^k n)}$ for some constant $k > 0$, where $\log^k n$ denotes $(\log n)^k$. Let us define QuasiP as the class of problems that can be solved in quasipolynomial time.

So presumably the definition for QuasiP could be written $TIME(\bigcup_k 2^{\Theta(\log^k n)})$. However every other definition I've found on the web, in particular the one from Wikipedia, suggests the alternative definition $TIME(\bigcup_k 2^{O(\log^k n)})$.
Now I can't see how these definitions are supposed to be equivalent. In fact I can imagine that there's a function $f$ that requires $2^{\log n}$ steps for even values of $n$ and $1$ step for odd values of $n.$ $f$ would fail to be in $2^{\Theta(\log^0 n)}$ because of the even values of $n$ and it would fail to be in $2^{\Theta(\log^k n)}$ for any $k > 0$ because of the odd values of $n$. However $f$ is still in $2^{O(\log^1 n)}$.
So apparently such an $f$ is in QuasiP according to the second definition but not according to the first. Did I make a mistake in the reasoning here? And if not am I correct in assuming that the definition in The Nature of Computation is erroneous?

$\endgroup$
  • 1
    $\begingroup$ Step 1: Make sure you and all the authors whose work you are reading mean the same thing when they writing something like "$2^{O(\dots)}$". $\endgroup$ – Raphael Jan 7 '17 at 19:08
6
$\begingroup$

The equality

$Time\left(\bigcup\limits_k 2^{O\left(\log^k n\right)}\right)= Time\left(\bigcup\limits_k 2^{\theta\left(\log^k n\right)}\right)$

is an equality betweeen two sets of languages decidable by certain Turing machines, and not an equality between sets of functions $f:\mathbb{N}\rightarrow\mathbb{N}$.

The function you constructed is an example of a function in $\bigcup\limits_k 2^{O\left(\log^k n\right)}\setminus \bigcup\limits_k 2^{\theta\left(\log^k n\right)}$, but this does not contradict the above equality.

Let $L\in Time\left(2^{O\left(\log^k n\right)}\right)$ for some $k\in\mathbb{N}$, be a language decidable by a Turing machine which runs in time $2^{O\left(\log^k n\right)}$. You can simply construct an equivalent Turing machine which runs in time $2^{\theta\left(\log^k n\right)}$ by adding redundant steps in case the computation ended too quickly, and this shows $L\in Time\left(2^{\theta\left(\log^k n\right)}\right)$.

$\endgroup$
  • $\begingroup$ So to put it in my own words, if $A$ is a set of functions then $TIME(A)$ doesn't denote the set of Turing machines who's running time is a member of $A$. Rather it denotes the set of Turing machines who's running time is bounded by some function in $A$. $\endgroup$ – Sebastian Oberhoff Jan 7 '17 at 18:09
  • $\begingroup$ @SebastianOberhoff No. Time(A) denotes a class of languages. $\endgroup$ – Raphael Jan 7 '17 at 19:09
  • $\begingroup$ Ok, but that adds just another level of indirection to the definition: If $A$ is a set of functions then $TIME(A)$ denotes the set of languages for which there exists a Turing machine deciding that language who's running time is bounded by some function in $A$. $\endgroup$ – Sebastian Oberhoff Jan 7 '17 at 20:24
  • 1
    $\begingroup$ $Time(A)$ is usually defined as the set of languages decidable by Turing machines whose running time is bounded by a function in $A$. What i was trying to convince you, is that even if you require the bound to be sharp, then this doesn't really matter and the equality remains true (this is done by constructing a new Turing machine, which decides the same language but uses more time). $\endgroup$ – Ariel Jan 7 '17 at 22:08
  • 1
    $\begingroup$ Now I see your point. I was only considering the optimal Turing machine for a given problem when in fact any Turing machine solving the problem will do. $\endgroup$ – Sebastian Oberhoff Jan 7 '17 at 22:36
6
$\begingroup$

Both definitions are equivalent, since when we say that a problem can be solved in time $t$, we usually mean that it can be solved in time at most $t$. For example, a problem can be solved in time $n$ if there is an algorithm solving it whose running time $T(n)$ satisfies $T(n) \leq n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.