User Jeffε

101 votes

2 answers

43k views

What is the actual time complexity of Gaussian elimination?

asked Dec 21, 2010 at 22:46

145 votes

2 answers

19k views

Super Mario Galaxy problem

asked May 2, 2011 at 0:01

130 votes

11 answers

12k views

How hard is unshuffling a string?

asked Aug 16, 2010 at 21:12

35 votes

5 answers

11k views

Is there a stable heap?

asked Aug 25, 2010 at 23:30

40 votes

3 answers

10k views

Is optimally solving the n×n×n Rubik's Cube NP-hard?

asked Aug 31, 2010 at 0:09

19 votes

2 answers

7k views

Complexity of computing the discrete Fourier transform?

asked Sep 12, 2011 at 14:33

41 votes

2 answers

6k views

Sum-of-square-roots-hard problems?

asked Jan 1, 2011 at 17:38

17 votes

2 answers

5k views

Time complexity of Bellman-Held-Karp algorithm for TSP, take 2

asked Dec 9, 2010 at 5:14

26 votes

2 answers

4k views

Exact number of comparisons to compute the median

asked Aug 9, 2012 at 17:15

21 votes

4 answers

2k views

Permutation game redux

asked Dec 29, 2011 at 13:19

27 votes

2 answers

2k views

Complexity of n-queens-completion?

asked Dec 29, 2014 at 23:06

31 votes

3 answers

2k views

Is it NP-hard to play international draughts correctly?

asked Oct 5, 2010 at 19:13

22 votes

2 answers

2k views

Detecting two kinds of almost-simple polygons

asked May 22, 2012 at 14:33

23 votes

1 answer

1k views

Complexity of computing shortest paths in the plane with polygonal obstacles

asked Dec 31, 2010 at 6:10

27 votes

1 answer

921 views

Other applications of Karger-Stein branching amplification?

asked Oct 23, 2010 at 20:37

20 votes

3 answers

830 views

Is it hard to find optimal addition chains?

asked Sep 3, 2010 at 15:49

12 votes

1 answer

601 views

Positive topological ordering, take 2

asked Sep 17, 2010 at 4:54

22 votes

1 answer

473 views

Exact planar electrical flow

asked Feb 14, 2013 at 15:59

13 votes

0 answers

375 views

Applications of an access lemma for dynamic forests?

asked Mar 16, 2011 at 6:02

7 votes

2 answers

287 views

Paths in a weighted line arrangement

asked Sep 21, 2010 at 16:13

10 votes

0 answers

243 views

Complexity of cycle cancellation with integral capacities and irrational costs

asked Mar 23, 2017 at 3:24

Stack Exchange Network

21 Questions

What is the actual time complexity of Gaussian elimination?

Super Mario Galaxy problem

How hard is unshuffling a string?

Is there a stable heap?

Is optimally solving the n×n×n Rubik's Cube NP-hard?

Complexity of computing the discrete Fourier transform?

Sum-of-square-roots-hard problems?

Time complexity of Bellman-Held-Karp algorithm for TSP, take 2

Exact number of comparisons to compute the median

Permutation game redux

Complexity of n-queens-completion?

Is it NP-hard to play international draughts correctly?

Detecting two kinds of almost-simple polygons

Complexity of computing shortest paths in the plane with polygonal obstacles

Other applications of Karger-Stein branching amplification?

Is it hard to find optimal addition chains?

Positive topological ordering, take 2

Exact planar electrical flow

Applications of an access lemma for dynamic forests?

Paths in a weighted line arrangement

Complexity of cycle cancellation with integral capacities and irrational costs