32 votes
Accepted

Least number of comparisons needed to sort (order) 5 elements

The solution is wrong. Demuth [1; via 2, sec. 5.3.1] shows that five values can be sorted using only seven comparisons, i.e. that the "information theoretic" lower bound is tight in this instance. ...
user avatar
  • 71k
22 votes
Accepted

How to prove that matrix multiplication of two 2x2 matrices can't be done in less than 7 multiplications?

This is a classical result of Winograd: On multiplication of 2x2 matrices. Strassen showed that the exponent of matrix multiplication is the same as the exponent of the tensor rank of matrix ...
user avatar
19 votes
Accepted

Is it really possible to prove lower bounds?

We can absolutely prove such things. Many problems have trivial lower bounds, such as that finding the minimum of a set of $n$ numbers (that are not sorted/structured in any way) takes at least $\...
user avatar
17 votes

How to prove that matrix inversion is at least as hard as matrix multiplication?

If you want to multiply two matrices $A$ and $B$ then observe that $$\begin{pmatrix}I_n&A&\\&I_n&B\\&&I_n\end{pmatrix}^{-1}= \begin{pmatrix}I_n&-A&AB\\&I_n&-B\\&...
user avatar
  • 1,151
14 votes

Is it really possible to prove lower bounds?

Yes, it's possible. The classic example is the fact that any comparison-based sorting algorithm requires $\Omega(n\log n)$ comparisons to sort a list of length $n$. However, lower bounds seem to be ...
user avatar
10 votes

In complexity, why do we find upper bounds, not lower bounds?

Lower bounds are of great interest and an active topic of research. However, we tend to be interested in lower bounds for problems and upper bounds for algorithms. An upper bound for an algorithm is ...
user avatar
10 votes
Accepted

$O(\frac{\log n}{\log \log n})$ algorithm for the prefix parity problem

I did a quick read over the paper you linked. Based on the ideas given in that paper, here's a simple data structure that obtains an $O(\frac{\log n}{\log\log n})$ time bound on each operation. You ...
user avatar
9 votes
Accepted

Is there an intuitive proof for the existence of hard functions?

As Pål GD mentions in his comment, the proof is actually very simple: there are $2^{2^n}$ functions, but only $C_S = S^{O(S)}$ circuits of size at most $S \geq n$. The exact constant in the exponent ...
user avatar
9 votes
Accepted

guillotine cuts versus general cuts

Although this is not tight, I can offer lower and upper bounds of $1/4$ and $3/4$ on the worst case ratio between guillotine cuts and general cuts. Let us start with the upper bound and assume we are ...
user avatar
9 votes

Problems that provably require quadratic time

Finding an envy-free cake-cutting requires $\Omega(n^2)$ queries. However, this does not directly answer your question as the computational model is different than a Turing machine. By the way, ...
user avatar
9 votes
Accepted

space complexity of DFA intersection problem

Solving intersection Non-Emptiness for 2 DFA's: It essentially just becomes a reachability problem for the product DFA. Roughly, we can solve it deterministically in $O(n^2)$ time using $O(n^2)$ ...
user avatar
9 votes
Accepted

Lower Bounds for Size of Independent Set in a Graph?

The relevant result is known as Turán's theorem. It states that if a graph has less than (roughly) $n(n-1)/(2r)$ edges then it has an independent set of size $r+1$, and this is tight.
user avatar
8 votes

What is the min # of moves to sort an array from 1 to n?

There is an invariant that each move can only increase the number in your longest increasing subsequence by at most 1. If your initial array has $k$ values in its longest increasing subsequence, you ...
user avatar
  • 201
8 votes
Accepted

Searching the space of permutations

Consider the following set of $n$ orders, which I give for $n = 6$: $$ 123456 \\ 213456 \\ 132456 \\ 124356 \\ 123546 \\ 123465 $$ Hopefully the generalization to arbitrary $n$ is clear. If you never ...
user avatar
8 votes
Accepted

Is Green's the best 16-input sorting network so far?

No, a lower bound means that somebody has proved that anything smaller than 53 is impossible. That doesn't mean that a 53-gate network is known or even necessarily possible; just that there cannot be ...
user avatar
8 votes
Accepted

Why is the lower bound of element uniqueness in $\Omega(n\log n)$?

We assume the comparison model in the lower bound of the element uniqueness problem. That is, the key operations are to compare elements. In particular, hashing is not allowed.
user avatar
  • 9,219
7 votes
Accepted

Are there any known lower-bounds for complexity on Non-determinsitic machines

No. There are no known polynomial bounds. The best lower bounds known are merely linear. As described here, the situation for circuits at least is "quite depressing": there are no known lower ...
user avatar
  • 143k
7 votes
Accepted

Complexity of sorting $A+A$

This answer assumes that your question is about computing the sorted order of $\{ x_i + x_j : 1 \leq i,j \leq n \}$ given a list $x_1,\ldots,x_n$. This problem is a special case of $X+Y$ sorting. ...
user avatar
7 votes

How to prove that matrix multiplication of two 2x2 matrices can't be done in less than 7 multiplications?

You can find the result at: S.Winograd, On multiplication of 2×2 matrices, Linear Algebra and Appl. 4 (1971), 381–388, MR0297115 (45:6173).
user avatar
7 votes
Accepted

Does finding a cycle with $\log n$ length in $\text{P}$?

You can use color-coding, a celebrated technique due to Alon, Yuster and Zwick.
user avatar
7 votes

What is Ironic complexity? What are some good resources to learn about it?

Here is a quote from Scott Aaronson's survey on the P vs NP question, in which he coined this term: There is one technique that has had some striking recent successes in proving circuit lower ...
user avatar
7 votes

What is an optimal algorithm?

There are various notions of optimality one can think of. One popular notion of optimality is worst-case running time, which is what you describe: An algorithm for solving a problem $P$ is ...
user avatar
6 votes
Accepted

Lower bound for finding majority element in a sorted array

Any algorithm would need $\Omega(\log n)$ queries. To see this, define $f(k)$ to be the number of queries needed for deciding whether an element $x$ appears at least $a$ times in a sorted array $A$. ...
user avatar
  • 2,594
6 votes
Accepted

Find the central point in a metric-space point set, in less than $O(n^2)$?

No. You can't do better than $\Theta(n^2)$ in the worst case. Consider an arrangement of points where every pair of points are at distance $1$ from each other. (This is a possible configuration.) ...
user avatar
  • 143k
6 votes

Using Context free language to simulate regular expression in finite automata

No such non-trivial bound can be obtained. Consider the language $L_n = \{ 0^{kn} : k \in \mathbb{N}\}$. Any NFA for $L_n$ needs at least $n$ states, but it can be generated by a context-free grammar ...
user avatar
6 votes

Is Green's the best 16-input sorting network so far?

The lower bound for an problem states that "no algorithm can do better than this". In your case, it means that no sorting network for 16 inputs can have fewer than 53 gates. Sometimes there can be ...
user avatar
  • 842
6 votes

Is there a decision algorithm with time complexity of Ө(n²)?

Yes: Checking that a string is a palindrome takes $\Omega(n^2)$ on a single tape Turing machine. In general the time hierachy theorem implies that there are such problems for most reasonable ...
user avatar
  • 5,910
6 votes

Prove a lower bound

Let me suggest direct simple solution: definition of $\Omega$ contains $2$ bound variables $c$ and $N$. In simple cases, as is in OP, we can choose one and solve second from expression obtained from ...
user avatar
  • 2,366
5 votes

In complexity, why do we find upper bounds, not lower bounds?

It isn't true that we are are more interested in upper bounds than lower bounds. Knowing the upper bound allows you to estimate whether your algorithm is feasible for a particular application. This ...
user avatar

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