Skip to main content
Ian's user avatar
Ian's user avatar
Ian's user avatar
Ian
  • Member for 13 years, 10 months
  • Last seen more than 12 years ago
25 votes

Can a computer simulate itself as part of a simulated world?

18 votes
Accepted

The structure of pathological instances for simplex algorithms

15 votes

what is easy for minor-excluded graphs?

2 votes
Accepted

Finding islands of vertices in a network of roads containing one-way streets

12 votes

Truly random number generator: Turing computable?

10 votes
Accepted

Properties of Random Directed Graphs with Fixed Out-Degree

5 votes
Accepted

A relaxed Steiner Tree Problem

9 votes

Have any generalizations of maximum weight matching been studied?

5 votes

Major conjectures used to prove complexity lower bounds?

10 votes

Are there NP-complete problems with polynomial expected time solutions?

17 votes

Are there alternatives to using polynomials in defining the different notions of efficient computation?

33 votes

The importance of Integrality Gap

22 votes
Accepted

Is APX contained in NP?

18 votes

Kolmogorov complexity applications in computational complexity