Ian
  • Member for 11 years, 5 months
  • Last seen more than 10 years ago
The importance of Integrality Gap
32 votes

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 ...

View answer
Can a computer simulate itself as part of a simulated world?
23 votes

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 ...

View answer
Is APX contained in NP?
Accepted answer
22 votes

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 ...

View answer
The structure of pathological instances for simplex algorithms
Accepted answer
17 votes

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 ...

View answer
Kolmogorov complexity applications in computational complexity
17 votes

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 ...

View answer
Are there alternatives to using polynomials in defining the different notions of efficient computation?
16 votes

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 ...

View answer
what is easy for minor-excluded graphs?
15 votes

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: ...

View answer
Truly random number generator: Turing computable?
11 votes

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 ...

View answer
Properties of Random Directed Graphs with Fixed Out-Degree
Accepted answer
10 votes

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)$. ...

View answer
Are there NP-complete problems with polynomial expected time solutions?
10 votes

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 ...

View answer
Have any generalizations of maximum weight matching been studied?
8 votes

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 ...

View answer
A relaxed Steiner Tree Problem
Accepted answer
5 votes

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 ...

View answer
Major conjectures used to prove complexity lower bounds?
5 votes

The unique games conjecture has recently been one of the most fruitful assumptions for proving good lower bounds, although it is more controversial than most assumptions about complexity class ...

View answer
Finding islands of vertices in a network of roads containing one-way streets
Accepted answer
2 votes

As Robin says, you want strongly connected components. They can be easily found using Tarjan's algorithm, Gabow's algorithm, or several others.

View answer