# Tag Info

41

The usual answer to "what could cause you to divide by a log?" is a combination of two things: a model of computation in which constant time arithmetic operations on word-sized integers are allowed, but in which you want to be conservative about how long the words are, so you assume $O(\log n)$ bits per word (because any fewer than that and you couldn't ...

35

The Rubik's Cube is a very natural (and to me, unexpected) example. An $n\times n\times n$ cube requires $\Theta(n^2/\log n)$ steps to solve. (Note that this is theta notation, so that's a tight upper and lower bound). This is shown in this paper . It may be worth mentioning that the complexity of solving specific instances of the Rubik's cube is open,...

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.

30

No. No unconditional better lower bound than the trivial $\Omega(n)$ is currently known for integer multiplication. There are some conditional lower bounds though. For more on this, you can have a look at Martin Fürer's paper Faster Integer Multiplication. Edit following Andrej's comment: Addition can be done in time $\mathcal O(n)$. In comparison, the ...

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

23

In general you cannot determine complexity, even for halting programs: let $T$ be some arbitrary Turing machine and let $p_T$ be the program (that always returns 0): input: n run T for n steps if T is in halting state, output: 0 otherwise, loop for n^2 steps and output: 0 It is clear that it is undecidable in general whether $p_T$ is linear-time or ...

23

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})$. ...

20

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

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

An example of $\log n$ showing up in the denominator without bit packing tricks is a recent paper by Agarwal, Ben Avraham, Kaplan and Sharir on computing the discrete Fréchet distance between two polygonal chains in time $O(n^2\log\log n/\log n)$. While I'm not familiar with the details of the algorithm, one general trick is to partition the input into ...

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

The lower bound is correct (2) - you can not do this better than $\Omega(n^2 \log n)$ and (1) is of course wrong. Lets us first define what is a sorted matrix - it is a matrix where the elements in each row and column are sorted in increasing order. It is now easy to verify that each diagonal might contains elements that are in any arbitrary order - you ...

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

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

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

Classical work of Coppersmith shows that for some $\alpha > 0$, one can multiply an $n \times n^\alpha$ matrix with an $n^\alpha \times n$ matrix in $\tilde{O}(n^2)$ arithmetic operations. This is a crucial ingredient of Ryan Williams's recent celebrated result. François le Gall recently improved on Coppersmith's work, and his paper has just been ...

13

Not exactly what you asked for, but a situation "in the wild" in which a log factor appears in the denominator is the paper "Pebbles and Branching Programs for Tree Evaluation" by Stephen Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, and Rahul Santhanam. The tree evaluation problem (TEP) is: given a $d$-ary tree annotated with values in $\{1,\ldots,k\}... 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 In the case of determinant, Gaussian elimination can indeed be seen as equivalent to the idea that the determinant has a large symmetry group (of a particular form) and is characterized by that symmetry group (meaning any other homogeneous degree$n$polynomial in$n^2$variables with those symmetries must be a scalar multiple of the determinant). (And, as ... 12 The problem is surprisingly non-trivial. Here is a nice solution by Ellis and Markov, In-Situ, Stable Merging by way of the Perfect Shuffle (section 7). Ellis, Krahn and Fan, Computing the Cycles in the Perfect Shuffle Permutation succeed in selecting "cycle leaders", at the expense of more memory. Also related is the nice paper by Fich, Munro and Poblete, ... 12 Consider the following algorithm (a variant of Levin's algorithm): Run the first$n$algorithms in parallel. Additionally, run in parallel a brute-force algorithm that tries all possible solutions one by one. (Run all algorithms with the same speed.) Stop when one of the algorithms finds a solution. Consider two cases (given an input$x$of length$n$):$...

12

Even though it's not about runtime, I thought it worth mentioning the classical result of Hopcroft, Paul, and Valiant: $\mathsf{TIME[t]} \subseteq \mathsf{SPACE}[t/\log t]$ , since it's still in the spirit of "what could cause you to save a log factor." That gives lots of examples of problems whose best known upper bound on space complexity has a log in ...

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