Skip to main content
Share Your Experience: Take the 2024 Developer Survey
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 ...
Christian Komusiewicz's user avatar
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" ...
Gamow's user avatar
  • 5,772
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 ...
usul's user avatar
  • 7,615
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 ...
Joshua Grochow's user avatar
17 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: ...
Martin Berger's user avatar
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. ...
D.W.'s user avatar
  • 12.1k
15 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$. ...
Huck Bennett's user avatar
  • 4,878
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 ...
Yuval Filmus's user avatar
  • 14.5k
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 ...
Ryan Williams's user avatar
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 ...
Ryan Williams's user avatar
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 ...
Robert Andrews's user avatar
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 ...
Lieuwe Vinkhuijzen's user avatar
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 ...
Dmytro Taranovsky's user avatar
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 $...
Andy Drucker's user avatar
  • 4,634
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{...
Mikhail Rudoy's user avatar
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 ...
usul's user avatar
  • 7,615
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 ...
Emil Jeřábek's user avatar
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, ...
Emil Jeřábek's user avatar
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 ...
Andrej Bauer's user avatar
  • 29.1k
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'...
Ryan Williams's user avatar
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 ...
Laakeri's user avatar
  • 1,786
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, ...
Joshua Grochow's user avatar
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 ...
Georg Zetzsche's user avatar
8 votes
Accepted

NEXPTIME-completeness with more time for reductions

The trouble with exponential-time reductions is that they may exponentially expand the input, and this leads to all sorts of weirdness. So, to begin with, neither EXP nor NEXP is closed under exp-time ...
Emil Jeřábek's user avatar
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$.
Gamow's user avatar
  • 5,772
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 ...
Trixie Wolf's user avatar
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 ...
M. kanté's user avatar
  • 1,046
8 votes
Accepted

Determining if a word of specific length exists that is not accepted by a NFA

Your problem is NP-hard, by reduction from 3SAT. Let $\varphi$ be a 3SAT formula with $m$ clauses and on the $n$ variables $x_1,\dots,x_n$. Construct a NFA over the alphabet $\Sigma=\{0,1\}$ as ...
D.W.'s user avatar
  • 12.1k
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/...
David Eppstein's user avatar
8 votes

What are some algorithms where space complexity tends to be the limiting factor in practice?

In knowledge compilation, the task is to compile some set $A\subseteq \{0,1\}^n$ into a format such that various queries can then be answered in polynomial time. For example, you can "compile&...
Lieuwe Vinkhuijzen's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible