# Tag Info

### 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 ...
• 50.3k
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 ...
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,722

### 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$-...
• 676
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

### 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 ...
• 35.8k
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 ...
• 5,444

### 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. ...
• 10.5k
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: ...
• 10.3k
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 ...
• 26.4k
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,090

### 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 ...
• 7,653

### 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 ...
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 ...
• 9,378
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.1k