Questions tagged [time-complexity]
Time complexity of decision problems or relations among time-bounded complexity classes. (Use the [analysis-of-algorithms] tag for the time taken by particular algorithms.)
395
questions
65
votes
10
answers
12k
views
One Stack, Two Queues
background
Several years ago, when I was an undergraduate, we were given a homework on amortized analysis. I was unable to solve one of the problems. I had asked it in comp.theory, but no ...
- 16.5k
46
votes
8
answers
21k
views
Complexity of Finding the Eigendecomposition of a Matrix
My question is simple:
What is the worst-case running time of the best known algorithm for computing an eigendecomposition of an $n \times n$ matrix?
Does eigendecomposition reduce to matrix ...
- 11.9k
44
votes
7
answers
5k
views
Using lambda calculus to derive time complexity?
Are there any benefits to calculating the time complexity of an algorithm using lambda calculus? Or is there another system designed for this purpose?
Any references would be appreciated.
- 2,233
26
votes
6
answers
2k
views
Advanced techniques for determining complexity lower bounds
Some of you may have been following this question, which was closed due to not being research level. So, I'm extracting the part of the question which is at a research level.
Beyond the "simpler" ...
- 2,830
24
votes
12
answers
3k
views
What are some algorithms where space complexity tends to be the limiting factor in practice?
Time complexity can't be any lower than space complexity (at least one operation is required to use a unit of memory), so what are some algorithms where space actually tends to be the limiting factor? ...
- 401
23
votes
2
answers
1k
views
To what extent can an algorithm predict the time complexity an arbitrary input program?
The Halting problem states that it is impossible to write a program that can determine if another program halts, for all possible input programs.
I can, however, certainly write a program that can ...
- 363
23
votes
3
answers
808
views
Adding integers represented by their factorization is as hard as factoring? Reference request
I'm looking for a reference for the following result:
Adding two integers in the factored representation is as hard as factoring two integers in the usual binary representation.
(I'm pretty sure ...
- 36.9k
23
votes
1
answer
2k
views
Can all unambiguous grammars be parsed in linear time?
When tinkering with noncanonical LR parsing, I thought up a parsing method (with infinitely sized tables, which makes it somewhat unpractical) capable of parsing exactly the unambiguous grammars in $O(...
- 4,670
22
votes
1
answer
2k
views
Is there a proof that addition is faster than multiplication?
The best upper bound known on the time complexity of multiplication is Martin Fürer's bound $n\log n2^{O(\log^* n)}$, which is more than linear time complexity of addition. Do we have a proof that ...
- 331
22
votes
2
answers
883
views
Multiplicative version of 3-SUM
What is known about the time complexity of the following problem, which we call 3-MUL?
Given a set $S$ of $n$ integers, are there elements $a,b,c\in S$ such that $ab=c$?
This problem is similar to ...
- 321
22
votes
1
answer
1k
views
Binary multiplication and parity convolution
This question is about the relationship between normal multiplication of binary numbers and polynomial multiplication mod 2. To make the question concrete, I would ideally like to know if there is a ...
- 3,950
21
votes
3
answers
3k
views
How much time to recognize palindromes in logarithmic space?
It is well-known that palindromes can be recognized in linear time on $2$-tape Turing machines, but not on single-tape Turing machines (in which case the time needed is quadratic). The linear-time ...
- 4,439
21
votes
5
answers
838
views
What notable automaton models have polynomially-decidable containment?
I'm trying to solve a particular problem, and I thought I might be able to solve it using automata theory. I'm wondering, what models of automata have containment decidable in polynomial time? i.e. if ...
- 2,830
19
votes
11
answers
2k
views
Are there any problems whose best known algorithm has run time $O\left(\frac{f(n)}{\log n}\right)$
I've never seen an algorithm with a log in the denominator before, and I'm wondering if there are any actually useful algorithms with this form?
I understand lots of things that might cause a log ...
- 1,063
19
votes
5
answers
1k
views
Why do relational databases work at all, given the theoretical exponential complexity of answer finding (in the size of the query)?
It seems to be known that to find an answer to a query $Q$ over a relational database $D$, one needs time $|D|^{|Q|}$, and one cannot get rid of the exponent $|Q|$.
As $D$ can be very large, we wonder ...
19
votes
1
answer
1k
views
Has parameterized complexity led to better algorithms?
I know that for the vertex cover problem, if we know that the parameter $k$ (which is the number of vertices in the solution) is small, then we can expect to solve it feasibly in practice. So far, ...
- 301
19
votes
1
answer
934
views
Time complexity with irrational exponent?
Is there any natural problem in P for which the best known running time bound is of the form $O(n^\alpha)$, where $\alpha$ is an irrational constant?
- 11.3k
19
votes
4
answers
3k
views
What is the "right" definition of upper and lower bounds?
Let $f(n)$ be the worst case running time of a problem on input of size $n$. Let us make the problem a bit weird by fixing $f(n) = n^2$ for $n=2k$ but $f(n) = n$ for $n=2k+1$.
So, what is the lower ...
- 331
19
votes
2
answers
2k
views
Runtime of Grover's algorithm
What is the time complexity (not query complexity) of Grover's algorithm? It seems clear to me that it is $\Omega(\log(N) \sqrt{N})$ since there are $\Omega(\sqrt{N})$ iterations and each iteration ...
- 493
19
votes
2
answers
2k
views
Is there a non-deterministic linear time algorithm for CNF-SAT?
The decision problem CNF-SAT can be described as follows:
Input: A boolean formula $\phi$ in conjunctive normal form.
Question: Does there exist a variable assignment that satisfies $\phi$?
I'm ...
- 5,127
18
votes
3
answers
1k
views
Trade off between time and query complexity
Working directly with time complexity or circuit lower bounds is scary. Hence, we develop tools like query complexity (or decision-tree complexity) to get a handle on lower bounds. Since each query ...
- 10.2k
18
votes
2
answers
7k
views
Complexity of computing the discrete Fourier transform?
What is the complexity (on the standard integer RAM) of computing the standard discrete Fourier transform of a vector of $n$ integers?
The classical algorithm for fast Fourier transforms, ...
- 23.1k
18
votes
2
answers
2k
views
"Almost sorting" integers in linear time
I am interested in sorting an array of positive integer values $L = v_1, \ldots, v_n$ in linear time (in the RAM model with uniform cost measure, i.e., integers can have up to logarithmic size but ...
- 8,896
17
votes
2
answers
436
views
similar matrices
Given two $n \times n$ matrices $A$ and $B$, the problem of deciding if there exist a permutation matrix $P$ such that $B = P^{-1}AP$ is equivalent to GI(Graph ...
- 1,281
16
votes
2
answers
1k
views
Is there a SETH (Strong Exponential Time Hypothesis) for CSP (Constraint Satisfaction Problem)?
The Constraint Satisfaction Problem I mentioned is similar to CNF-SAT: A variable can take values from some finite domain $D$ where $|D| = d$. A literal of variable $x$ is an expression of the form $x\...
- 163
16
votes
1
answer
531
views
Can you decide equivalence for monotone Boolean expressions that do not contain negation in PTIME?
Is the following problem in PTIME, or coNP-hard:
Given two Boolean expressions $e_1$ and $e_2$ in variables $x_1,\dots,x_n$, without negation (ie, the expressions are entirely built up via $\wedge$ ...
- 288
16
votes
2
answers
6k
views
What is the fastest algorithm to compute rank of a rectangular matrix?
Given an $m \times n$ matrix (assuming $m \ge n$), what is the fastest algorithm to compute its rank and basis of the columns?
I am aware it can be solved through linear matroid intersection, which ...
- 163
16
votes
0
answers
216
views
What is the background in algebraic geometry and representation theory needed for geometric complexity theory? [duplicate]
I'm a mathematics student in my junior year and I'm interested in computational complexity and specially geometric complexity theory. I'm going to learn algebraic geometry and representation theory ...
- 269
15
votes
4
answers
3k
views
Counting the number of vertex covers: when is it hard?
Consider the #P-complete problem of counting the number of vertex covers of a given graph $G = (V, E)$.
I'd like to know if there is any result showing how the hardness of such problem varies with ...
- 6,780
15
votes
3
answers
907
views
Can we compute $n$ from the bits of $3^n$ in $O(n)$ time?
I'm seeking an efficient algorithm for the problem:
Input: The positive integer $3^n$ (stored as bits) for some integer $n \geq 0$.
Output: The number $n$.
Question: Can we compute $n$ from the bits ...
15
votes
3
answers
3k
views
Linear time in-place riffle shuffle algorithm
Is there a linear time in-place riffle shuffle algorithm? This is the algorithm that some especially dextrous hands are capable of performing: evenly dividing an even-sized input array, and then ...
- 153
15
votes
1
answer
385
views
Does $∩_{ε>0} \mathrm{DTIME}(O(n^{2+ε})) = \mathrm{DTIME}(n^{2+o(1)})$?
I expect the answer is no, but I could not actually construct a counterexample. The difference is that in $∩_{ε>0} \mathrm{DTIME}(O(n^{2+ε}))$, we might not be able to pick an $O(n^{2+ε})$ ...
- 2,537
15
votes
0
answers
486
views
An algebra of complexity classes
A key feature of unrelativized computation is its composability out of smaller fragments, and to partially capture the composability, I came up with an algebra of fine-grained complexity classes.
For ...
- 2,537
14
votes
1
answer
797
views
Is Quasi-polynomial time in PSPACE?
I had done some search on this but I was not able to find an answer either way.
Huck answered it fully. Thanks :)
- 2,579
14
votes
3
answers
2k
views
Lower Bounds for Data Structures
Are results known which rule out the existence of "too-good-to-be-true" data structures?
For example: can one add $Split$ and $Join$ functionality to an order maintenance data structure (see Dietz ...
- 800
14
votes
3
answers
3k
views
What is a natural problem in theory of computation?
In Stephen Cook's paper on the P vs NP problem,[1] he states the following [2]:
Feasibility Thesis: A natural problem has a feasible algorithm iff it has a polynomial-time algorithm.
My question ...
- 143
14
votes
2
answers
1k
views
Gaussian Elimination in terms of Group Action
Gaussian elimination makes determinant of a matrix polynomial-time computable. The reduction of complexity in computing the determinant, which is otherwise sum of exponential terms, is due to ...
- 1,281
14
votes
1
answer
1k
views
Distinguishing between two coins
It is well known that the complexity of distinguishing an $\epsilon$ biased coin from a fair one is $\theta(\epsilon^{-2})$. Are there results for distinguishing a $p$ coin from a $p+\epsilon$ coin? I ...
- 373
14
votes
1
answer
8k
views
The computational complexity of matrix multiplication
I am looking for information about the computational complexity of matrix multiplication of rectangular matrices. Wikipedia states that the complexity of multiplying $A \in \mathbb{R}^{m \times n}$ by ...
- 149
14
votes
1
answer
1k
views
Are there languages decidable in linear time by RAM machines that have superlinear time complexity lower bounds for Multitape Turing machines?
Question: Are there languages decidable in linear time by RAM machines that have superlinear time complexity lower bounds for Multitape Turing machines?
Background: I recently stumbled upon the ...
- 5,127
14
votes
1
answer
987
views
Equivalent definitions of time constructibility
We say that a function $f:\mathbb{N}\rightarrow\mathbb{N}$ is time-constructible, if there exists a deterministic multi-tape Turing machine $M$ that on all inputs of length $n$ makes at most $f(n)$ ...
- 532
13
votes
6
answers
617
views
Any algorithmic problem has a time complexity dominated by counting?
What I refer to as counting is the problem that consists in finding
the number of solutions to a function. More precisely, given a
function $f:N\to \{0,1\}$ (not necessarily black-box), approximate
$\#...
- 960
13
votes
3
answers
5k
views
Examples of problems where exponential algorithms run faster than polynomial algorithms for practical sizes?
Do you know of any problems (preferably at least somewhat well known), where, for a practical problem size, an exponential algorithm runs much faster than a best-known polynomial time counterpart.
...
- 313
13
votes
2
answers
889
views
Complexity of Membership-Testing for finite abelian groups
Consider the following abelian-subgroup membership-testing problem.
Inputs:
A finite abelian group $G=\mathbb{Z}_{d_1}\times\mathbb{Z}_{d_1}\ldots\times\mathbb{Z}_{d_m}$ with arbitrary-...
13
votes
2
answers
370
views
General collection with the current state of complexity bounds of well-known unsolved problems?
Most classical computer science problems are still open concerning the exact asymptotic algorithmic worst-case complexity required to solve them.
Is there any online collaborative wiki (or other ...
- 131
13
votes
2
answers
2k
views
Reversing a list using two queues
This question is inspired by an existing question about whether a stack can be simulated using two queues in amortized $O(1)$ time per stack operation. The answer seems to be unknown. Here is a more ...
- 1,458
13
votes
1
answer
602
views
NEXPTIME-completeness with more time for reductions
One thing that surprised me when learning about complexity theory is that for a complexity class C, we tend to define C-complete using polynomial time reductions, even when C is a very large ...
- 233
13
votes
2
answers
265
views
Is the exponent in the rectangular matrix multiplication convex?
My question is regarding the paper "Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor". In the paper, the authors show an algorithm for multiplying a ...
- 630
13
votes
2
answers
2k
views
What's the most efficient algorithm for Divisibility?
What is the most efficient (in time complexity) algorithm known nowadays for the Divisibity Decision Problem: given two integers, say $a$ and $b$, does $a$ divide $b$? Let it be clear that what I ask ...
- 341
13
votes
0
answers
533
views
Lock-free, constant update-time concurrent tree data-structures?
I've been reading a bit of the literature lately, and have found some rather interesting data-structures.
I have researched various different methods of getting update times down to $\mathcal{O}(1)$ ...
- 566