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.)
46
questions
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
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
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
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
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
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
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
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
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
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
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
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
8
votes
1
answer
484
views
Are there more polynomial time problems with complexity lower bounds?
I'm looking for more problems in $P$ with classical time complexity lower bounds. Some people might wonder how you could prove such a lower bound. See below.
Exponential Lower Bounds:
Claim: If ...
- 5,127
7
votes
1
answer
437
views
Formalization of proofs and computational complexity paradox?
While reading some articles on formal proofs (see also my previous question on cstheory about the length of ZFC proofs versus human written proofs), I came up with this apparent paradox.
Let $M_{...
- 22.6k
6
votes
0
answers
845
views
Is this permutation-sum problem NP-complete?
A new, tighter tardiness bound has been found for global Earliest-Deadline-First scheduling of jobs on symmetric multiprocessors. But this bound seems to be particularly hard to compute. In particular,...
6
votes
2
answers
1k
views
Do runtimes for P require EXP resources to upper-bound? … are concrete examples known? (answer: yes and yes)
Update #6:
Wow, quick service on TCS StackExchange! Emanuele Viola has provided an answer Are runtime bounds in P decidable? Answer: No.
Emanuele's answer illuminates (for me) Luca Trevisan's ...
- 1,506
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
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
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 ...
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
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
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 ...
12
votes
1
answer
558
views
Does Kannan's theorem imply that NEXPTIME^NP ⊄ P/poly?
I was reading a paper of Buhrman and Homer “Superpolynomial Circuits, Almost Sparse Oracles and the Exponential Hierarchy”.
On the bottom of page 2 they remark that the results of Kannan imply that $...
Lorraine
12
votes
1
answer
3k
views
Complexity of converting a boolean circuit to a boolean formula
Given a boolean circuit $C$ on $n$ variables (which uses just NOT,AND and OR gates), what is the most efficient way to extract the boolean formula represented by the circuit? Is there a polytime ...
- 1,344
11
votes
2
answers
4k
views
Complexity of Finding the Eigendecomposition of a *Symmetric* Matrix
This is a specialized version of a previous question:
Complexity of Finding the Eigendecomposition of a Matrix .
For NxN symmetric matrices, it is known that O(N^3) time suffices to compute the ...
- 111
10
votes
1
answer
314
views
Is this language recognizable by a 3 symbols TM in O(n log n)?
I was playing with the very interesting and still open question "Alphabet of single-tape Turing machine" (by Emanuele Viola) and came up with the following language :
$L = \{ x \in \{0,1\}^n \text{ s....
- 22.6k
8
votes
2
answers
836
views
What is the initialization time of a link-cut tree?
Link-cut tree is a data structure invented by Sleator and Tarjan, which supports various operations and queries on a $n$-node forest in time $O(\log n)$. (For example, operation link combines two ...
- 7,638
8
votes
1
answer
315
views
Is there a relation between BBH (black box hypothesis) and SETH (strong exponential time hypothesis)?
Is there a relation between BBH (black box hypothesis) and SETH (strong exponential time hypothesis)?
- 91
8
votes
1
answer
367
views
Determining if a word of specific length exists that is not accepted by a NFA
It is known that the problem of determining if an NFA accepts every word is PSPACE-COMPLETE, meaning it is also NP-Hard, but is this weaker version of the problem still NP-hard?
Given an NFA and a ...
- 113
7
votes
2
answers
356
views
Given a subset of the hypercube and a copy translated by s, find s
Problem: Suppose we are given an $n$ element subset $A\subseteq\{0,1\}^d$ of the $d$ dimensional hypercube and a translated copy $B= A+s$ by some secret $s\in\{0,1\}^d$. Find $s$ as fast as possible ...
- 173
7
votes
2
answers
384
views
Are space and time hierarchies even comparable?
I am wondering if there are any results to what extent the space and time hierarchies "disagree" on which problem is harder. For example, is it known whether there are languages $L_1$ and $L_2$ such ...
- 643
6
votes
2
answers
3k
views
Complexity of the halting problem
One of the most celebrated results in computer science is that the halting problem is undecidable. However there are still notions of complexity that are applicable. Here are 3 that I have in mind:
$...
- 2,151
6
votes
2
answers
419
views
3SUM Complexity—A special(?) Case
In the paper “Consequences of Faster Alignment of Sequences” by
Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann which appeared in ICALP 2014 and is available here the following version of ...
- 2,070
6
votes
0
answers
204
views
Small universal monotone Turing machines
This paper surveys small universal Turing machines. What are some examples of small universal monotone Turing machines, as described by Schmidhuber? Which of these are efficient (polynomial time) ...
- 652
5
votes
0
answers
853
views
Nondeterministic linear time vs. the deterministic time hierarchy
How much is known about nondeterministic linear time? I'm aware that $$ \mathrm{NTIME}(n) \neq \mathrm{DTIME}(n).$$
Is there an $m > 1$ so that $\mathrm{NTIME}(n) \not\subset \mathrm{DTIME}(n^m)$? ...
- 1,206
5
votes
0
answers
166
views
Real-time countable vs fully time-constructible
Real-time countable functions were used in time hierarchy theorem in the papers of Hartmanis and Stearns (Theorem 9, 9.1 ...) and also of Hennie and Stearns (Theorems 3, 5, 7 ...). Now it is a "...
- 532
5
votes
2
answers
402
views
Are there problems in $DTIME(n^k) - DTIME(n^{k-1})$ that are not hard for $DTIME(n^{k-1})$ under nearly linear time reductions?
Background
It can be challenging to find computational problems that are solvable in $DTIME(n^k) - DTIME(n^{k-1})$ where $k \geq 2$.
Although some natural problems are known to exist, many of them ...
- 5,127
5
votes
0
answers
410
views
How are lower bounds for computational complexity proved? [closed]
As the title says, how are lower bounds for computational complexity proved? I'm interested why it is possible to say that a certain algorithm cannot run in faster time than some lower bound.
...
- 79
4
votes
0
answers
286
views
The problem of whether or not every function computable in time $T(n)$ is computable in time $T(n)^{O(1)}$ and space $T(n)^{o(1)}$ simultaneously
If a function is computable in time $T(n)$, is it computable in time $T(n)^{O(1)}$ and space $T(n)^{o(1)}$ simultaneously?
We won't be able to prove it, because it implies the open problems $\text{P} ...
- 548
4
votes
0
answers
128
views
Deciding transitivity of a directed acyclic graph [duplicate]
Is there any algorithm that decides whether a given directed acyclic graph is transitive or not, in time-complexity asymptotically better than boolean matrix multiplication?
- 399
4
votes
2
answers
175
views
Function with space-depending computation time
Does a function exist which is easily computable for one space capacity and is hard to compute for another? I am looking for a function which can be computed in polytime when available space is at ...
- 41
2
votes
2
answers
220
views
Problem in deterministic time $n^p$ and not lower
I'm looking for any language $L$ candiate to be in $DTIME(n^p) -DTIME(n^{p-1})$ (it takes at least $n^{p-1}$ steps to determine if an input is in L with a 2-tape $TM$, but L is polynomially solvable).
...
- 149
2
votes
1
answer
337
views
Finding max of two elements in linear time with restriction
I have a matrix in the following form:
...
- 131
2
votes
4
answers
6k
views
Complexity of greedy coloring
I was looking at some heuristics for coloring and found this book on Google books: Graph
Colorings By Marek Kubale
They describe the Greedy algorithm as follows:
...
- 247