Integrality gaps essentially represent the inherent limits of a particular linear or convex relaxation in approximating an integer program. Generally, if the integrality gap of a particular ...

No, a computer cannot perfectly simulate itself in addition to something else without violating basic information theory: there exist strings which are not compressible. Here's the simplest possible ...

APX is defined as a subset of NPO, so yes, if an optimization problem is in APX then the corresponding decision problem is in NP. However, if what you're asking is whether an arbitrary problem must ...

Amenta and Ziegler proved that all currently-known constructions of exponential-time instances for simplex follow a particular structure that they call "deformed products": Deformed Products and ...

Lance Fortnow has written an article on this topic: Kolmogorov Complexity and Computational Complexity You should also check out An Introduction to Kolmogorov Complexity and Its Applications by Li ...

From the very beginning $P$ has drawn flak for allowing high degree polynomials to count as efficient (Edmonds essentially introduced $P$ to argue that his $O(n^4)$ matching algorithm should be ...

There are a number of papers showing various NP-hard problems can be approximated significantly better (either $O(1)$ or PTAS) on excluded-minor graphs than on general graphs. See, for instance: ...

Intuitively, "random" means "unpredictable", and any sequence generated by a Turing machine can be predicted by running the machine, so Turing machines cannot produce "truly random" numbers. There ...

In the undirected case random $d$-regular graphs are expanders with high probability (not for $d=2$, but I think $d \ge 3$ suffices), which implies that the mixing time of random walks is $O(\log n)$. ...

Regarding your last question on whether the existence of a good average case algorithm would imply the existence of a good worst-case algorithm: this is a major open question that is particularly of ...

There are several extensions of the problem to more general structures. For instance: Matroid matching (lecture notes, Matroid matching and some applications, Matroid Matching: the Power of Local ...

As in Robin's answer, I'll use the parameter $c$ to denote the minimum number of terminals that we are required to connect. Robin's response already answers your question for most values of $c$, but ...