user avatar
user avatar
user avatar
SamM
  • Member for 10 years, 4 months
  • Last seen this week
35 votes

Are there any problems whose best known algorithm has run time $O\left(\frac{f(n)}{\log n}\right)$

12 votes

Does NP-completeness/hardness have to be constructive?

10 votes
Accepted

Complexity of Portal 2

10 votes

Is the problem of finding operators to satisfy a list of boolean variables NP complete?

10 votes
Accepted

Attempted proofs of P vs NP

6 votes

$O(m+n)$ really necessary for graph algorithms?

5 votes

Can any program be implemented mechanically?

4 votes

Is there a generalization of the GO game that is known to be Turing complete?

4 votes
Accepted

Ordered-file maintenance

4 votes
Accepted

A counting subset sum problem with fixed subset size and bounded weights

4 votes

Efficient algorithm to find overlapping circles of various sizes

3 votes

For which problems in P is it easier to verify the result than to find it?

3 votes

Problems that are easy on unweighted graphs, but hard for weighted graphs

2 votes

Polynomial time algorithm to solve the TSP on an m by n solid grid

2 votes
Accepted

Does this pairwise independent random process have expected max load $\sqrt{n}$?

2 votes

Cover a Concave Polygon with a minimum number of rectangles

1 vote

Decision version of matrix multiplication problem

1 vote

Examples of Computer-Found Optimal Strategies in Games

1 vote
Accepted

Inclusion probability of irregularly shaped polygon