34 votes

Magic constant to solve NP-complete problem in polynomial time

Probably not. What you are asking is whether NP $\subset$ P/poly. If this were true, then the polynomial hierarchy would collapse (this is the Karp–Lipton theorem), something that is widely believed ...
user avatar
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 ...
user avatar
24 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" ...
user avatar
  • 5,722
22 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$-...
user avatar
  • 676
22 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, ...
user avatar
  • 2,295
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 ...
user avatar
16 votes
Accepted

What notable automaton models have polynomially-decidable containment?

Visibly pushdown automata (or nested word automata, if you prefer working with nested words instead of finite words) extend the expressive power of deterministic finite automata: the class of regular ...
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. ...
user avatar
  • 10.5k
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: ...
user avatar
15 votes
Accepted

The hardness of generating an instance of a problem that is harder than the complexity of the resulting problem

This situation comes up frequently in crypto, where you want to generate hard problem instances along with their solutions. For example, there is the work of Eric Bach (and later, Adam Kalai) on ...
user avatar
15 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 ...
user avatar
  • 7,090
14 votes

What notable automaton models have polynomially-decidable containment?

If infinite words are in your scope, you can generalize DFA (with parity condition) to the so-called Good-for-Games automata (GFG), that still have polynomial containment. A NFA is GFG if there is a ...
user avatar
  • 7,653
14 votes

Generalized Geography on graphs of bounded treewidth

The proof in my 1989 paper does not rely on the fact that the graph is undirected. Directed treewidth is a different notion than the treewidth of the undirected graph obtained by changing each arc to ...
user avatar
13 votes
Accepted

Examples of problems where exponential algorithms run faster than polynomial algorithms for practical sizes?

How bout the simplex algorithm for linear programming? In many occasions it is used in practice. Edited to add: I think it's more of a "worse-case exponential algorithm" which runs ...
user avatar
  • 9,378
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 ...
user avatar
  • 14.1k
12 votes

Examples of problems where exponential algorithms run faster than polynomial algorithms for practical sizes?

The fastest algorithm known for the problem of identifying whether a graph has a knotless embedding is due to Miller and Naimi, and is exponential-time. Robertson-Seymour theory says that there is an $...
user avatar
11 votes
Accepted

Runtime of Grover's algorithm

The question is usually taken to be moot, for the following reason. Grover's algorithm is a combinatorial search algorithm to find a solution to an arbitrary predicate. While, yes, $\Theta(\log N)$ ...
user avatar
11 votes

What notable automaton models have polynomially-decidable containment?

A Non deterministic XOR automaton (NXA) fits your question. A NXA $M$ is essentially an NFA, but a word $w\in \Sigma^*$ is said to be in $L(M)$ if it is accepted by an odd number of paths (Xor ...
user avatar
  • 9,378
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 ...
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 ...
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 ...
user avatar
10 votes
Accepted

Generalized Geography on graphs of bounded treewidth

So, in short, the question is, since QBF is PSPACE-complete for bounded pathwidth formulas, why isn't Geography PSPACE-complete for bounded pathwidth graphs? I think the problem with this hardness ...
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 ...
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 ...
user avatar
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{...
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 ...
user avatar
  • 7,090
9 votes

What is the asymptotic time complexity of the number of steps of "Half Or Triple Plus One" ( HOTPO)?

By request, two facts that are known and seem somewhat related to your question. As a lower bound: infinitely many integers $n$ take time $\Omega(\log n)$. Applegate and Lagarias. As a sort of an ...
user avatar
9 votes
Accepted

Time complexity of d-dimensional convex hull

I don't know any nontrivial lower bounds other than the $\Omega(n\log n)$ algebraic-decision-tree lower bound for two dimensions, which also extends to larger $d$. As for upper bounds: In 3d, the ...
user avatar
9 votes
Accepted

Max flow: either saturate an edge or avoids

This problem is NP-hard. Reduction from PARTITION: Given a set of numbers $S=\{x_1,\ldots,x_n\}$, construct the following flow network: $$V = \{s,v,t\}\cup \{x_1,\ldots,x_n\}$$ $$E = \{(s,x_i) | ...
user avatar
  • 9,378
9 votes

Complexity of finding even cuts for a graph

Such a cut exists if and only if the graph has an even number of spanning trees, which can be checked in polynomial time by using the matrix-tree theorem. See http://www.ics.uci.edu/~eppstein/pubs/Epp-...
user avatar

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