Questions tagged [lower-bounds]
The lower-bounds tag has no usage guidance.
241
questions
0
votes
0
answers
39
views
Circuit Lower bound for $EXP^{NP}$
By Burhman, Fortnow and Thierauf result Paper Link, we know that $MA_{EXP} \not\subset P/poly$.
Also, we know that $MA \subseteq P^{NP}$ (or $\Delta_{2}^{P}$ in some literatures).
By using the ...
- 323
2
votes
1
answer
169
views
Tight bound on the number of intersections between a line and a triangulation
I'm interested in the maximum number of intersections that a line and a triangulation on $n$ points could have. More specifically, given $n$, we are interested in the worst-case (maximum) number of ...
- 427
21
votes
2
answers
4k
views
How to prove that matrix multiplication of two 2x2 matrices can't be done in less than 7 multiplications?
In Strassen's matrix multiplication, we state one strange ( at least to me) fact that matrix multiplication of two 2 x 2 takes 7 multiplication.
Question : How to prove that it is impossible to ...
- 1,157
4
votes
4
answers
2k
views
Is $Ω(n\log n)$ the lower-bound for *all* sorting algorithms or *just comparison-based* sorting algorithms?
Is $Ω(n\log n)$ the lower-bound for all sorting algorithms or just comparison-based sorting algorithms?
If the latter, is it possible for there to be general-purpose sorting algorithms which perform ...
- 421
2
votes
1
answer
306
views
"Natural" reductions vs "Polynomial-time many-one" reductions (Karp Reductions)
For two problems $A$ and $B$ and a Karp Reduction $R$ from $A$ to $B$, we call the reduction $R$ natural if, for any instance $I$ of problem $A$, the size of $R(I)$ (as well as the possible numerical ...
- 323
6
votes
1
answer
2k
views
How to prove that matrix inversion is at least as hard as matrix multiplication?
Suppose we are given a matrix $A$ over real numbers and we want to computer the inverse of matrix $A$. There are various algorithms to do so and it also turn out that we can use matrix multiplication ...
- 1,157
0
votes
1
answer
104
views
Find a subset in constant many queries
Black box of $f(x)$ means I can evaluate the polynomial $f(x)$ at any point.
Input: A black box of monic polynomial $f(x) \in\mathbb{S}[x]$ of degree $d$.
Question : $\mathbb{S} \subseteq \mathbb{Z}$,...
- 1,157
1
vote
1
answer
7k
views
how to find upper bound and lower bound of quadratic equation
I am relatively new to algorithms, I wrote one pattern matching algorithm and its running time is $O(n^2)$, I tried it by step count method, direct method and also the constant method which all yields ...
- 121
1
vote
1
answer
1k
views
Best Algorithm for searching for an index in an array such that A[i] = i
Recently i got a question in one of my exams about asking for an algorithm which searches an element in a sorted array such that $A[i] = i$. My algorithm was based on binary search and did a $O (\log ...
1
vote
0
answers
445
views
Reductions: Lower Bound and Upper Bound
The question is from my complexity-theory course.
Explain the concept of polynomial reduction between problems and explain how, and under what circumstances, lower bound and upper bound problems can ...
- 169
1
vote
1
answer
109
views
Lower bounds: Detecting a length 2 path
Prove that determining if a non-directed graph of $n$ vertices has or doesn't have a length $2$ path requires time $\Omega(n^2)$, assuming that the graph is represented as an adjacency matrix.
4
votes
1
answer
167
views
Proving that converting min-heaps to max-heaps requires time Ω(n)
Suppose I have a min-heap SH stored inside an array. I can perform the operations:
view-min(SH) in $O(1)$
extract-min(SH) in $O(\log n)$
insert(SH) in $O(\log n)$
is-empty(SH) in $O(1)$
If I want to ...
- 459
2
votes
1
answer
419
views
Doubt regarding address calculation in two-dimensional arrays
I am reading about the address calculation formulas for one and two-dimensional arrays. I have two related doubts concerning it.
In one of the problems, we are asked to calculate the ...
- 121
2
votes
1
answer
233
views
Lower bound on space of DFS keeping the running time linear
$\mathsf{DFS(G, u) \text{}}$, $G = (V,E)$
Input : A Directed graph $G$ and a source vertex $u$.
Find : Is $v$ reachable from vertex $u$ for all $v \in V$ ?
Model of computation : Word RAM , one ...
user35837
5
votes
1
answer
2k
views
Complexity of determining whether three points are collinear from a set of points
Let $S \subseteq \mathbb{R}^2$ be a finite set of points. Do there exists three collinear points $p, q, r \in S$?
I wan't to know the complexity of this decision problem and present my approach as ...
- 389
2
votes
1
answer
295
views
Lower Bound for Sorted 2-Sum
Given a sorted array of integers $x$ and a target value $t$, determine if there exists a pair $x_i, x_j \in x \wedge i \neq j$ such that $x_i + x_j = t$.
What is the lower bound for this problem?
I ...
- 4,391
5
votes
1
answer
158
views
Lower bound of degree of polynomial approximating parity
Let $\text{MOD}_2 : \{0,1\}^n \rightarrow \{0,1\}$ be a parity function where $$\text{MOD}_2(x_1,\dots,x_n) = \sum_i x_i \bmod 2$$
It is known [See e.g. Lemma 5 of this lecture note] that any ...
- 283
0
votes
1
answer
991
views
How to solve a knapsack problem with increased weight limit?
Let us consider the knapsack problem. Given a set $P$ of $n$ items where each item has weight $w_i$ and value $v_i$ for all $i=1,2,\ldots,n$. We have two bins, one has a weight limit of $W$ and the ...
- 693
2
votes
0
answers
150
views
Finding post-order traversal of a binary tree from its in-order and pre-order traversals lower bound
I know that we can construct a BST by just having its pre-order traversal in $O(n)$ time (this link). But what if the tree is just a binary tree and we have its in-order and pre-order traversals? I ...
- 81
3
votes
1
answer
180
views
Evasiveness of acyclicity of undirected graph
The lecture note by Jeff Erickson discusses "Evasive Graph Properties":
We call a graph property evasive if we have to look at all $\binom{n}{2}$ entries in the adjacent matrix to decide whether ...
- 9,441
1
vote
1
answer
1k
views
Can we count the number of inversions in time $\mathcal{O}(n)$?
It is possible to find the total number of inversions by $\mathcal{O}(n\log{}n)$ running time (extension of merge-sort algorithm for example).
Is there more asymptotically efficient way to do it? $\...
- 205
0
votes
1
answer
753
views
Lower bound on worst case pancake number?
Given n pancakes, for each permutation we can compute the minimum number of pancake flips. If we take the maximum over all possible permutations, we get the worst case pancake number $P_n$.
I think ...
- 119
1
vote
1
answer
333
views
Why is the lower bound $m \log n$ for this make-set, union and find-set sequence?
Look at this solution:
Is the lower bound $m\log n$ because we are only looking at the lower bound for union by rank only? If we make $n$ MAKE-SET operations, then there would be $\log n$ UNION ...
- 13
3
votes
1
answer
2k
views
Lower bound for $k$-sorting an array
This is exercise 2 of the lecture note by Jeff Erickson on decision tree lower bounds.
We say that an array $A[1 \ldots n]$ is $k$-sorted if it can be divided into $k$ blocks, each of size $n/k$ (we ...
- 9,441
3
votes
1
answer
93
views
Original literature on adversary argument
I want to know about the early invention/use of the adversary argument (see the lecture note by Jeff Erickson) which is a technique for establishing lower bounds of problems.
I cannot find the ...
- 9,441
6
votes
1
answer
866
views
(Nontrivial) Algorithms for finding the third largest element of a set
According to the lecture note by Jeff Erickson, the lower bound for finding the third largest element of a set of $n$ distinct elements is open. See the related post: What is the lower bound for ...
- 9,441
4
votes
3
answers
2k
views
Why is the lower bound of element uniqueness in $\Omega(n\log n)$?
I wish to discuss the element uniqueness problem. First let's define the problem:
Definition from wikipedia:
In computational complexity theory, the element distinctness problem
or element ...
- 255
2
votes
1
answer
657
views
Lower bound on the number of comparisons needed for finding the two largest elements
Given a sequence of ݊different elements, there is an algorithm that finds the maximum element, and the 2nd largest element, using n +log_2(n) - 2 comparisons. Prove that any algorithm will have to ...
- 21
3
votes
1
answer
449
views
How to prove that Inner product of two $n$ dimensional vectors requires at least $n$ many multiplications?
Input : Two matrices $A$ and $B$ of size $n$ X $n$.
Compute : Matrix product $A$ X $B$.
Some of the known results about matrix multiplication are given below.
Brute Force : $O(n^3)$.
Nader H. ...
user35837
4
votes
1
answer
305
views
lower bound for Renyi–Ulam Game with lies
Player $A$ thinks of number between 1 and $n$ and ask $B$ to guess the number with minimum number of decision queries (yes or no type ).
Game :
$A$ chooses an element in {1,2....,n}
$B$ tries to ...
user35837
5
votes
1
answer
297
views
Size of constant depth circuit for digital comparator?
Is a lower bound of $\Omega(n^2)$ known for the size of any constant depth circuit expressing a digital comparator for two $n$-bit numbers?
Two $n$-bit binary numbers can be compared using a digital ...
- 3,422
2
votes
1
answer
173
views
Why is $\Omega(\log\log n)$ a lower bound for the depth of polynomial-width circuits computing parity?
I'm working on an exercise from The Nature of Computation concerning polynomial-width circuits computing parity. In particular the exercise asks to sketch a proof that the depth of such a circuit has ...
- 1,048
4
votes
1
answer
1k
views
Determining if an integer appears more than $n/2$ times
What is the minimum number of comparisons required to determine if an integer appears more than $n/2$ times in a sorted array of $n$ integers?
I am trying binary search on the array A.
Algorithm(A): ...
user35837
1
vote
1
answer
504
views
Sorting using comparison is superlinear or sublinear?
My question is, is comparison based sorting problem, in time complexity, a superlinear problem or a sublinear problem?
In more details: we know that sorting using comparison have the achievable lower ...
- 11
2
votes
1
answer
1k
views
Precise relation between complexity classes(focus on P, NP and EXPTIME)
I am interested in the precise relation between $P$, $NP$ and $EXPTIME$ classes.
What I know so far:
$P \subseteq EXP$ (from Time Hierarchy Theorem [1])
We don't know an exact relation between $P$ ...
MihaiM
1
vote
1
answer
2k
views
How to use the Pigeonhole Principle to prove a DFA has a minimum number of states?
$A = \{w \in \{a, b\}^* | $ 10th character from the end of $w$ is $b\}$
Prove if DFA $M$ has $L(M) = A$ then $M$ has at least 1024 states.
So there's only 2 characters possible at any state, aside ...
- 31
3
votes
1
answer
103
views
Complexity of sorting $A+A$
Is there a proof for the lower bound of the problem to create a sorted list of sums for a given list of integers with length n.
In this [thread][1] people discuss solving this problem by sorting the ...
- 149
-1
votes
2
answers
1k
views
Deleting edges from complete graph
I have a complete undirected graph with $V$ vertices and $\frac{V(V - 1)}{2}$ edges. Then, I remove $K$ edges $(a_i, b_i)$. I want to know if the graph is still connected after performing all the ...
- 223
2
votes
1
answer
132
views
Examples for lower bounds proof except sorting
After i read this question here.
All non-trivial examples of lower bounds always mention sorting, but i do not find other non-trivial examples, which do not rely (partly) on the sorting proof.
What ...
- 21
3
votes
1
answer
998
views
Is there a decision algorithm with time complexity of Ө(n²)?
Is there a decision problem with a time complexity of Ө(n²)?
In other words, I'm looking for a decision problem for which the best known solution has been proven to have a lower bound of N².
I ...
0
votes
1
answer
614
views
Adding Big-O and little-o notation to get a little-o
Lets suppose that there exists a comparison-based algorithm that turns an arbitrary array to a state $A$ in $o(n\log k)$, and there is another comparison-based algorithm that turns an array in state $...
2
votes
1
answer
171
views
Linear time algorithms on regular graphs
For each constant $k$, the number of $k$-regular graphs is of the order of $n^{\Omega(n)}$. Therefore, we need $O(n\log n)$ bits to represent k-regular graphs unambiguously.
Let $k=3$ for simplicity....
- 21
0
votes
1
answer
56
views
What is the best terminology for lower bound
The term lower bound comes from math and applies to more than just complexity theory. What we see is that such and such is "a" lower bound. In complexity theory should this not be phrased as "the" ...
- 51
0
votes
2
answers
241
views
Sorting algorithm which sorts half the possible inputs in linear time
Prove that there isn't any comparison sort algorithm which for an input of size $n$ can sort at least half of the permutations of the input in linear time.
(For the other half the algorithm can ...
- 722
5
votes
3
answers
863
views
Is Green's the best 16-input sorting network so far?
Every paper says that Green's construction is the best 16-input sorting
network as for now.
But why does Wikipedia says: "Size, lower bound: 53"?
I thought "lower bound" meant:"If there exists at ...
- 153
0
votes
0
answers
25
views
What are some quadratic run time tasks (algorithms)? [duplicate]
Are there problems, for which best algorithms have worst run time O(input_length^2) and it is proven, that this worst time cannot be substantially improved (better algorithms do not exist).
EDIT: ...
- 484
6
votes
1
answer
180
views
Are there any known lower-bounds for complexity on Non-determinsitic machines
For some problems, like sorting, we know that on a deterministic RAM Machine, any comparison sort must take at least $\Omega(n\log n)$ time.
Are they any problems where we have known lower bounds for ...
- 29.5k
1
vote
1
answer
71
views
How often can a linear speed sort succeed?
Let's say you have sorting function. It is allowed to exit with failure (but if it does not it must return a correctly sorted sequence). It is also $\mathcal O (n)$.
What kind of bounds can we place ...
- 766
2
votes
1
answer
90
views
Replacing n with 2n in asymptotic bounds
I am going through Normal Subgroup Reconstruction and Quantum Computation Using Group Representations by Hallgren et al.
In the proof of the theorem $6$ of the paper on page 632, the authors go on ...
- 326
2
votes
1
answer
226
views
How to give an upper bound on this bin packing problem?
In the bin packing with fragile objects (BPFO) problem one is given a set of objects $\{1,\ldots,n\}$ where each object $i$ has a weight $w_i$ and a fragility $f_i$ for all $i$ in the set $\{1,\ldots,...
- 960