26
votes
Accepted
Has parameterized complexity led to better algorithms?
There are several examples of problems where a parameterized algorithm performs well in practice. Let me mention two such problems.
In the $k$-Path problem where we are looking for a simple path of ...
- 1,700
25
votes
Accepted
How "hard" is it to maximize a polynomial function subject to linear constraints?
Your problem is NP-hard, even for polynomials of degree 2.
The crucial reference is
Theodore Motzkin and Ernst Strauss (1965)
"Maxima for graphs and a new proof of a theorem of Turan"
...
- 5,772
23
votes
Using lambda calculus to derive time complexity?
A recent developpement on this topic: U. dal Lago and B. Accatoli proved that the length of the leftmost-outermost reduction (LOr) of a $\lambda$-term is an invariant (time) cost model for $\lambda$-...
- 686
21
votes
Accepted
Time complexity with irrational exponent?
While admittedly I haven't done the analysis, and this is not strictly a decision problem, I am willing to wager the best known matrix multiplication algorithms (by Coppersmith, Winograd, Stothers, ...
- 2,295
19
votes
Accepted
What is a natural problem in theory of computation?
To be clear, it's not meant to be formalizable. It's not a theorem, it's an observation about the world -- it's okay if "natural" is subjective here. For analogy, if someone says "differentiation is ...
- 7,595
19
votes
What are some algorithms where space complexity tends to be the limiting factor in practice?
Most computations in algebraic geometry / commutative algebra.
Most involve computing Grobner bases, which are EXPSPACE-hard in general. There are some parameter regimes where this improves and thus ...
- 36.9k
16
votes
Data structure to determine if sets are disjoint in o(n) time
The communication complexity of the set disjointness problem is $\Omega(n)$. The communication complexity is a lower bound on the time complexity of testing whether the two instances are disjoint. ...
- 11.7k
16
votes
Accepted
Equivalent formulation of complexity theory in Lambda Calculus?
As you point out, the λ-calculus has a seemingly simple notion of time-complexity: just count the number of β-reduction steps. Unfortunately, things are not simple. We should ask:
...
- 11.4k
13
votes
Accepted
questions on implications Babais quasi P time graph isomorphism result
Johnson graphs are actually easy to recognize. In particular, you can recognize whether an input graph is a Johnson graph in polynomial time, and you can construct an isomorphism between two ...
- 14.3k
13
votes
Accepted
Is there a SETH (Strong Exponential Time Hypothesis) for CSP (Constraint Satisfaction Problem)?
This CSP is known to be SETH-hard. More precisely, assuming SETH, for any constant $\varepsilon > 0$ there is no $d^{(1-\varepsilon)n}$-time algorithm for solving this CSP with domain size $d$.
...
- 4,788
11
votes
Are there languages decidable in linear time by RAM machines that have superlinear time complexity lower bounds for Multitape Turing machines?
It depends on the precise definition of RAM being used, but (for most reasonable definitions of RAMs) this would also imply that SAT is not solvable in $O(n^{2-e})$ time by multitape TMs, a ...
- 27.3k
11
votes
Lower-bounds under SETH
Most problems need at least linear time, so $O(n \log n)$ may be a little too close to optimal for a SETH based lower bound, generally we want running times where one can improve on the exponent by ...
- 27.3k
11
votes
Are there any problems whose best known algorithms have running time $n^{\log \log n}$?
The best-known deterministic algorithm for testing polynomial identities given by depth-three diagonal circuits has running time $n^{O(\log \log n)}$ [1].
More explicitly, we are given an expression ...
- 743
10
votes
What is the complexity of the fastest method of k-coloring any graph?
There are non-obvious improvements over simple brute-force search for $k$-coloring (and for many other NP-hard problems). The obvious approach would take roughly $k^n$ time, but one can do it in time $...
- 4,634
10
votes
Accepted
Does $∩_{ε>0} \mathrm{DTIME}(O(n^{2+ε})) = \mathrm{DTIME}(n^{2+o(1)})$?
Here is a counterexample, i.e. a language with an $O(n^{2+ε})$ algorithm (using multitape Turing machines) for every $ε>0$, but not uniformly in $ε$:
Accept $0^k 1^m$ iff $k>0$ and the $k$th ...
- 2,537
10
votes
Quantum polynomial hierarchy vs counting hierarchy
I was quite surprised as well to not find this hierarchy in the literature, so I wrote my graduate thesis about it. It will be available online soon, at which point I will update this answer with a ...
- 1,944
10
votes
Accepted
Are space and time hierarchies even comparable?
You can get the situation you describe by choosing weird functions $f(n)$ and $g(n)$.
For example, let $g(n) = n^3$ and $$f(n) = \begin{cases}
n & \text{if $n$ is odd},
\\\
2^{n^5} & \text{...
- 2,758
10
votes
Is there a non-deterministic version of the complexity class PP?
PP is defined as a probabilistic class and we don't normally think of nondeterministic versions of any of these classes (as far as I'm aware). In a sense probabilistic classes and nondeterministic ...
- 7,595
9
votes
Accepted
Formalization of proofs and computational complexity paradox?
$\def\mc{M_\mathit{const}}\def\mp{M_\mathit{paradox}}$Let me for the record write up the answer to Q1, so that it doesn’t live only in the comments.
The reasoning given in steps 1–5 in the question ...
- 16.9k
9
votes
Accepted
Is there a non-deterministic version of the complexity class PP?
It does not really make sense to define an “X-version of class Y”, this is a misguided viewpoint. You define classes because they are useful or interesting in whatever context you are investigating, ...
- 16.9k
9
votes
Equivalent formulation of complexity theory in Lambda Calculus?
Counting $\beta$-reductions is one kind of complexity measure for $\lambda$-calculus, but a more flexible and reasonable one is cost semantics, where the operational semantics is augmented by various ...
- 28.3k
9
votes
Accepted
Is there a relation between BBH (black box hypothesis) and SETH (strong exponential time hypothesis)?
Adding to Sasha's answer. Roughly speaking, BBH posits that every property of functions that is hard to decide with only query access to the function (black box access) is also hard to decide when you'...
- 27.3k
9
votes
Accepted
Implication of solving 3SUM problem of a certain size on the Exponential Time Hypothesis
I think currently it is not even known if strong ETH and 3SUM are related, see e.g. [1]. For the relation of ETH and 3SUM, note that ETH really cannot be refuted by improving polynomial time ...
- 1,767
9
votes
Are there any problems whose best known algorithms have running time $n^{\log \log n}$?
The best-known algorithm for testing isomorphism of finite groups whose solvable radical is either (a) contained in the center or (b) elementary abelian, is $n^{O(\log \log n)}$. These are, ...
- 36.9k
8
votes
Definition of near-linear algorithm
A natural definition of "near-linear" should be:
A function $f:\mathbb{N}\to\mathbb{N}$ is near-linear, if $~f(n)\in O(n^{1+\varepsilon})~$ for all $\varepsilon>0$.
- 5,772
8
votes
Accepted
Can emptiness of reversal-bounded counter languages be decided in time polynomial to the number of counters?
If the number of counters or the number of reversals (or both) is part of the
input, the problem becomes coNP-complete (unless there is exactly one counter):
The upper bound was shown by Hague and ...
- 351
8
votes
Runtime of Grover's algorithm
Turns out that there is a way to implement Grover's algorithm with fewer than $O(\sqrt{N}\log N)$ gates! That's why you were not able to find a reference claiming that $\Omega(\sqrt{N}\log N)$ gates ...
- 13.5k
8
votes
"Almost sorting" integers in linear time
This sounds a lot like the ASort algorithm. See this article by Giesen et. al.:
https://www.inf.ethz.ch/personal/smilos/asort3.pdf
Unfortunately, the running time is not quite linear. The article ...
- 181
8
votes
Accepted
Is counting simple cycles in $P$ for graphs of bounded tree width?
A simple cycle is a connected set where every vertex has degree 2. Then you have a formula SC(X) stating X (a set of edges) is a simple cycle. You can see many versions of Courcelle's theorem for ...
- 1,046
8
votes
What are some algorithms where space complexity tends to be the limiting factor in practice?
My go-to answer for this (the one I use in undergraduate algorithms classes) is the Bellman–Held–Karp dynamic programming algorithm for the traveling salesperson problem (https://en.wikipedia.org/wiki/...
- 50.9k
Only top scored, non community-wiki answers of a minimum length are eligible