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
