Tag Info

4

Yamakami showed in their paper Analysis of Quantum Functions that the quantum analog of PP is the same as classical PP. This is mentioned in the Wikipedia article on PP.

3

There is no one true answer. It depends on context. The most common context is one where polynomial-time is taken as more or less synonymous with efficient, so if you had no further context, I would certainly guess "polynomial time". Polylogarithmic time is used only in very narrow contexts. In general, if you think your audience might not be sure about ...

3

The complexity class $\Sigma_2^P$, which is the second level of the polynomial hierarchy, consists of all languages $L$ for which there exists a polytime predicate $f$ and a polynomial $p$ such that $$x \in L \Longleftrightarrow \exists y \forall z \, f(x,y,z), \text{ where } |y|,|z| \leq p(|x|).$$ This is the natural location for your problem: $x$ is a ...

2

Sipser reduces $A_{\mathit{TM}}$ to $\mathit{HALT}_{\mathit{TM}}$. Since $A_{\mathit{TM}}$ is uncomputable, it follows that $\mathit{HALT}_{\mathit{TM}}$ has to be uncomputable. He is using the following general statement: If $A$ reduces to $B$ and $B$ is uncomputable, then so is $A$. You are right that this general statement itself is proved by ...

2

You're right. All that matters is that the reduction runs in polynomial time. (It follows that the circuit has polynomial size, since the output of any polynomial-time algorithm must be polynomial in length.) Given a circuit with multiple inputs, you can force some of the inputs to 0 or 1. If the circuit has polynomial size, this modification takes ...

1

No, $\sqrt{n}$ increases far faster than $O(1)$, and $n^{\sqrt{n}}$ grows far faster than $n^{O(1)}$. No, it certainly does not have the same runtime. See Sorting functions by asymptotic growth. There may be no predefined complexity class; the complexity class is the class of all algorithms who run in time $n^{O(\sqrt{n} \log n)}$, and there's probably ...

Only top voted, non community-wiki answers of a minimum length are eligible