# 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
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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.
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 ...
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 ...
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 ...
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 ...
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)$ ...
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 ...
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 ...
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 :)
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 ...
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 ...
437 views

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_{... 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 ... 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" ... 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 ... 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 ... 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 ... 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+ε})$... 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$... 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 ...
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 ...
314 views

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 ...
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) ...
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)$? ...
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 "...
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 ...
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. ...
286 views