Most Popular
1500 questions
22
votes
1 answer
Solving semidefinite programs in polynomial time
We know that linear programs (LP) can be solved exactly in polynomial time using the ellipsoid method or an interior point method like Karmarkar's algorithm. Some LPs with super-polynomial (exponential) number of variables/constraints can also be…
Arindam Pal
- 1,591
- 12
- 23
22
votes
1 answer
Algorithms and structural complexity theory
Many important results in computational complexity theory, and in particular "structural" complexity theory, have the interesting property that they can be understood as fundamentally following (as I see it...) from algorithmic results giving an…
Ashley Montanaro
- 2,013
- 18
- 21
22
votes
3 answers
Number of distinct nodes in a random walk
Commute time in a connected graph $G=(V,E)$ is defined as the expected number of steps in a random walk starting at $i$, before node $j$ is visited and then node $i$ is reached again. It is basically the sum of the two hitting times $H(i,j)$ and…
Fabrizio Silvestri
- 353
- 1
- 9
22
votes
1 answer
Natural, untestable graph properties
In graph property testing, an algorithm queries a target graph for the presence or absence of edges and needs to determine whether the target either has a certain property or is $\epsilon$-far from having the property. (An algorithm can be asked to…
Lev Reyzin
- 11,968
- 13
- 63
- 103
22
votes
1 answer
Is there a proof that addition is faster than multiplication?
The best upper bound known on the time complexity of multiplication is Martin Fürer's bound $n\log n2^{O(\log^* n)}$, which is more than linear time complexity of addition. Do we have a proof that addition is inherently easier than multiplication?
Hooman
- 331
- 2
- 7
22
votes
2 answers
Polynomial time approximation algorithms for machine scheduling: how many open problems are left?
In 1999, Petra Schuurman and Gerhard J. Woeginger published the paper "Polynomial time approximation algorithms for machine scheduling: Ten open problems". Since then, to the best of my knowledge, reviews which would concern very the same list of…
Oleksandr Bondarenko
- 4,215
- 1
- 25
- 46
22
votes
4 answers
What are infinite graphs good for?
I have just read on the German Wikipedia that an infinite graph is a graph with an infinite number of nodes or an infinite number of edges. I only know applications and algorithms for finite graphs.
What are infinite graphs good for?
What are…
Martin Thoma
- 615
- 8
- 15
22
votes
2 answers
Lower bounds for constant-depth formulae?
We know a lot about the limitations of (polynomial size) constant-depth circuits. Since (polynomial size) constant-depth formulae are an even more restricted model of computation, all problems known not to be in AC0 are also not computable by a…
Robin Kothari
- 13,617
- 2
- 60
- 116
22
votes
2 answers
Detecting two kinds of almost-simple polygons
I'm interested in the complexity of deciding whether a given non-simple polygon is almost simple, in either of two different formal senses: weakly simple or non-self-crossing. Since these terms are not widely known, let me start with some…
Jeffε
- 23,129
- 10
- 96
- 163
22
votes
1 answer
Generating a tower defense maze, aka Finding the K most vital nodes ("nodewise interdiction") in an unweighted grid-graph
In a tower defense game, you have an NxM grid with a start, a finish, and a number of walls.
Enemies take the shortest path from start to finish without passing through any walls (they aren't usually constrained to the grid, but for simplicity's…
BlueRaja - Danny Pflughoeft
- 1,591
- 3
- 13
- 19
22
votes
3 answers
Why do we use single tape Turing machines for time complexity?
As you know there are many anomolies for the single tape Turing machines when the time is $o(n^2)$: multi-tape TM simulation, simulation of larger tape alphabet with just $\{0,1,b\}$, time constructability, non-tightness of time hierarchy theorem,…
Kaveh
- 21,577
- 8
- 82
- 183
22
votes
2 answers
Are AND&OR circuits P-complete?
The AND&OR gate is a gate which is given two inputs and returns their AND and their OR. Are circuits made only out of the AND&OR gate, without fanout, capable of doing arbitrary computations? More precisely, is polynomial time computation logspace…
Itai Bar-Natan
- 537
- 2
- 5
22
votes
4 answers
Where do most REGEX implementations fall on the complexity scale?
Most modern implementations of regular expressions, such as the ones in perl or .NET, go beyond the classical computer science definition of REGEXes with features like lookahead and lookbehind. Do these features let them parse statements that can't…
Dan Monego
- 323
- 2
- 6
21
votes
3 answers
Approximate sum of a sorted list
Recently, I worked on the problem for computing the approximate sum of a list of sorted nonnegative numbers. For any fixed $\epsilon>0$, an $O(\log n)$ time approximation scheme has been derived such that it gives an $(1+\epsilon)$-approximation…
Bin Fu
- 674
- 4
- 8
21
votes
4 answers
Permutation game redux
This is a restatement of an earlier question.
Consider the following impartial perfect information game between two players, Alice and Bob. The players are given a permutation of the integers 1 through n. At each turn, if the current permutation…
Jeffε
- 23,129
- 10
- 96
- 163