34

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 not to happen.


26

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 length $k$. Alon, Yuster and Zwick [1] showed that this problem can be solved in $2^{O(k)}\cdot n$ time on $n$-vertex graphs. A weighted version of $k$-Path has ...


25

You can use the same argument used to prove the $\Omega(n^2)$ time bound on single tape. Suppose that you have a TM with $S(n)$ space that recognize palindromes $\{x\,0^{\frac{n}{3}} x^R \mid |x|=n/3 \}$ (where $x^R$ is the reverse of $x$) in time $T(n)$. When the (input) head crosses the middle $0^{n/3}$ it can carry only $S(n)$ bits of information. So it ...


24

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" Canadian Journal of Mathematics 17, pp 533-540 Motzkin and Strauss consider an undirected graph $G=(V,E)$ with vertex set $V=\{1,2,\ldots,n\}$. They show that ...


22

Using crossing sequences or communication complexity it is simple to derive the tradeoff $T(n)S(n) = \Omega(n^2)$ for a sequential Turing machine using time $O(T(n))$ and space $O(S(n))$. This result was first obtained by Alan Cobham using crossing sequences in the paper The recognition problem for the set of perfect squares which appeared at SWAT (later ...


22

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, Williams, et al) have irrational exponent. This can be seen more clearly in the simple case of Strassen's algorithm, which has running time $O(n^{\log_2 7})$. ...


21

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$-calculus. They show that Turing machines (with cost=time) and $\lambda$-terms (with cost=length of the LOr) can simulate each other with a polynomial overhead ...


19

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 some computations can reasonably be done in practice (e.g. using Macaulay2 or SINGULAR), but very often it quickly eats up all the space and crashes. I think ...


17

Lower bounds for algebraic circuits In the setting of algebraic circuits, where a lower bound on circuit size is analogous to a lower bound on time, many results are known, but there are only a few core techniques in the more modern results. I know you asked for time lower bounds, but I think in many cases the hope is that the algebraic lower bounds will one ...


16

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 languages is strictly contained within the class of visibly pushdown languages. For deterministic visibly pushdown automata, the language inclusion problem can ...


16

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. Imagine Alice stores the data structure for the first set, and Bob stores the data structure for the second set; since they'll have to communicate $\Omega(n)$ ...


15

I suggest you use the framework found in the following paper: How Far Can We Go Beyond Linear Cryptanalysis?, Thomas Baignères, Pascal Junod, Serge Vaudenay, ASIACRYPT 2004. The crucial result says that you need $n \sim 1/D(D_0 \,||\, D_1)$, where $D(D_0 \,||\, D_1)$ is the Kullback-Leibler distance between the two distributions $D_0$ and $D_1$. Expanding ...


15

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 efficiently generating random integers with their prime factorizations. One of many interesting observations of Impagliazzo and Wigderson (Randomness vs time: ...


15

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: Is counting β-reduction steps a good complexity measure? To answer this question, we should clarify what we mean by complexity measure in the first place. One good answer is ...


15

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 mechanics while integration is art", they're not inviting you to formalize "mechanics" and "art" and prove the statement, they're trying to convey a general ...


14

One area where unconditional and nontrivial time lower bounds are known is in data structures, where the time is for individual data structure operations (or sequences of operations). The standard model for this sort of thing is called the "cell probe model"; it assumes only that main memory is divided into words of a certain size and that the CPU has a very ...


14

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 strategy $\sigma:A^*\times Q\times A\to \Delta$, that given the prefix read so far and the current state and letter, chooses a transition to go to the next ...


14

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 an edge.


13

The obvious approach is: (1) Compute an approximation to $\log_2(3^n)$. You can approximate it to within an additive error of 1 by counting the number of bits in the given binary representation, and to within an additive error of $\epsilon$ by additionally looking at the top $O(\log\frac{1}{\epsilon})$ bits of the input. It should suffice to choose a ...


13

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 efficiently on practical instances/distributions rather than runs faster on practical sized adversarial instances.


13

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 isomorphic Johnson graphs in polynomial time. Johnson graphs come into the proof in a different way. Very roughly speaking, the proof juggles between group-theoretic ...


12

From the comment: In "Deterministic Turing Machines in the Range between Real-Time and Linear-Time" I found: ... if $r \in T^{−1}(DTM)$ and $r' \in o(r)$ then $DTIME(n+r') \subset DTIME(n+r)$ ...


12

Kaveh has gently suggested in his answer that I should say something. I don't have much else to contribute to this nicely comprehensive list of answers. I can add a few generic words about how "structural complexity" lower bounds have evolved over the past ten years or so. (I use the name "structural complexity" simply to distinguish from algebraic, ...


12

If you're asking whether a quantum computer can compute any function that a classical computer can compute without using many more elementary computational steps, then the answer is yes: a quantum computer can perform any reversible classical computation, and if you keep the input around, any classical computation can be made reversible at a cost of ...


12

For any integer $n>0$, writing $3^n$ in binary requires exactly $L = \lceil \log_2(3^n)+1\rceil$ bits. Some elementary algebra implies that $$ \frac{L-2}{\log_2 3} \le n \le \frac{L-1}{\log_2 3}. $$ For any bit length $L\ge 1$, there is at most one integer in this range. Thus, given an integral power of $3$ that is $L$ bits long, the exponent must be ...


12

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 $O(n^3)$ algorithm for this problem; however, to write it down we would need to know the list of forbidden minors for knotless embeddings. However, even if we ...


11

Ok, so as I understand it, you are given as input an undirected graph (representing the "within range" restrictions) with weights on its vertices, and you want to find a non-adjacent pair of vertices that has maximum total weight. I'm going to interpret linear time as being linear in the number of edges in the input graph, not just the number of vertices, ...


11

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)$ is the quantum gate complexity in each stage of the black-box algorithm, the predicate needs to be computed too. The quantum gate complexity of that is $\...


11

This version of the answer incorporates feedback from Emil Jeřábek. As far as I can see, the main twist is that there is a language in $\mathsf{EXP}^{\Sigma^\mathsf{P}_2}$ of exponential circuit complexity. In particular, fix a binary encoding of boolean circuits and define $L$ as the language defined by $L_n$ is not decided by any circuit of size $2^{n/2}$,...


11

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 relation) instead of being accepted if there exists an accepting path for it (Or relation). NXAs are used for creating small representations of regular languages as ...


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