# Tag Info

3

Part I: There probably aren't historical examples. Imagine an $\mathsf{NP}$-complete problem $Q$ with at most one reasonable polynomial-time algorithm, $A$. If ZFC fails to prove that $A$ solves $Q$, then $\mathsf{P}=\mathsf{NP}$ is independent of (unprovable from) ZFC. In section 3.1 of this paper Scott Aaronson analyzes this possibility quite extensively; ...

2

I think the issue here is a confusion re: partial vs. total computable functions. (Below I fix some "appropriate ambient axiom system," say $\mathsf{ZFC}$ - so e.g. "theorem" means "$\mathsf{ZFC}$-theorem" and so on.) Something which is often insufficiently emphasized in my experience is the extent to which partial (= defined on ...

2

The problem here is that the version of the Master theorem you have simply isn't strong enough to cover the case you are interested in of $$T(n)=4T(n/2)+n(\log n)^{12}.$$ This is because you need to use $f(n)\in\Theta(n^k)$ for some $k$; you can't deal with functions that look like $n^k(\log n)^\ell$. (I assume $n(\log n)^{12}$ is what's meant here, since $n\... 2 The short answer: gate number. What I mean by that is that is the number of physical gates used in the quantum algorithm is what is counted for complexity classes. Source: this is what I study and that is what we count for complexity purposes. If you want a little more information, you could try googling BQP. This is the set of problems which can be solved ... 2 In general, the best way (in my opinion) to manipulate$O$-expressions in multiplication/division/logarithms is to convert the absolute error$g(x) + O(h(x))$into a relative error$g(x) \big( 1 + O\big( h(x)/g(x) \big) \big)$. For example, the general shape of your function is $$\frac{f(x)}{g(x) + O(h(x))} = \frac{f(x)}{g(x)} \frac1{1 + O( h(x)/g(x) )}.$$ ... 2 For every$n\ge 1$, let$k(n)$be such that$2^{k(n)}\le n< 2^{k(n)+1}$. The point of this definition is that we can write$\mathbb N_+$as an "interleaving" $$\mathbb N_+ = \bigcup_{k\ \text{even}}[2^k,2^{k+1})\cup\bigcup_{k\ \text{odd}}[2^k,2^{k+1}).$$ Define $$f(n) = \begin{cases} n^{k(n)+1} & \text{if k(n) is even}\\ n^{k(n)} & \... 1 It's definitely not NP-Hard. For each vertex y, let N(y) be the set of vertices u such that uy is an arc in G. Then the cheapest path C(y,k+1) from s to y with at most k+1 arcs satisfies$$C(y,k+1)=\min_{u \in N(y)} [C(u,k)+c(uy)].$$The length of the longest path is at most$n$. So if each vertex$y$can keep track of$C(y,k)$for$k=1,.......

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