# 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
Filter by
Sorted by
Tagged with
260 views

### How would proof of the Lindelöf hypothesis improve our understanding of computational complexity classes?

A recent press release from the Viterbi School of Engineering at USC discussed the proof of the Lindelöf hypothesis by Athanassios Fokas, a visiting professor from the Department of Applied ...
121 views

### Finding upper and lower bounds of a problem [closed]

We have n balls where 1 is a little heavier than the others and we want to find that heavier ball. We can only put some balls on one side of the scale and some on the other side and see if it leans ...
437 views

250 views

429 views

### Most general setting for fine-grained exponential-time complexity classes?

Consider the class of functions computable in time $(b+o(1))^n = 2^{\log_2{(b)} \times n + o(n)}$ on a $2$-tape Turing machine. By the Hennie-Stearns theorem, the same functions are computable in ...
411 views

### Examples of quasilinear vs. essentially linear time translatable models

The Hennie-Stearns theorem says that $k$-tape Turing machines with $k \ge 2$ are intertranslatable with loglinear blowup ($O(t \times \log{(t)}$). This would define an equivalence class of models, ...
1 vote
601 views

### What is the time complexity of base conversion on a multi-tape Turing machine?

Base conversion is the problem of converting an integer between representations in two fixed bases. Without loss of generality consider the case of relatively prime bases. I think it's easier to ...
897 views

### What happens when PSPACE contains NEXP?

The complexity class NEXP is defined as the set of all languages that an arbitrary nondeterministic exponential time Turing Machine accepts (i.e. NTIME($2^{p(n)}$) for $p()$ a polynomial). In the ...
227 views

### What is the time complexity of increasing the precision of finding matrix eigenvalues?

There are various algorithms that output the eigenvalues of an $n \times n$ matrix in time $O(n^3)$. However, I can't find anywhere that tells me about the precision of the output of the algorithm. ...
191 views

### Complexity of finding semi-ordered Eulerian tours in a 4-regular graph

I'm trying to figure out the time-complexity of the problem I describe below, which I call the semi-ordered Eulerian tour problem or the SOET problem. Either finding an efficient algorithm for this ...
253 views

### When studying the computational complexity of functions $\{0, 1\}^\ast \to \{0, 1\}^\ast$, is it enough to restrict to $\{0, 1\}^\ast \to \{0, 1\}$?

I started reading Avi Wigderson's paper $\mathcal{P}$, $\mathcal{NP}$ and Mathematics – a Computational Complexity Perspective (link). (Notation: $\{0, 1\}^\ast$ is the set of all finite binary ... 370 views

### Complexity of the mandelbrot set on rationals

(Also posted on mathoverflow) Given two rationals $a,b \in \mathbb{Q}$, call $c = a + ib$, i.e., the complex number represented by these two rationals. A point $c$ is contained within the Mandelbrot ...
307 views

1 vote
77 views

### Best Asymptotic Complexity for Persistent Union Find

In this paper https://www.lri.fr/~filliatr/ftp/publis/puf-wml07.pdf, they claim to have a practically fast persistent union-find data structure for most use-cases, but it's still not polylogarithmic ...
1 vote
119 views

### Computing $a^e \mod p^n$ Efficiently

It is well known that we can compute: $$a^e \mod m$$ in $O(\log e \log ^2 m)$ bit operations (assuming multiplication $nm$ in $O(\log n \log m)$ time) via exponentiation by squaring. I am wondering ...
1k views

### What is the complexity of the fastest method of k-coloring any graph? [closed]

I heard brute-force is the only method. Is there any other way? Is there a way to prove that the complexity cannot be exponential?
649 views

### Efficient all pair bottleneck computation for a tree

Consider a weighted tree $T = (V,E)$. The bottleneck weight for a pair of vertices $v_1,v_2 \in V$ is the highest weight of the edges on the unique path from $v_1$ to $v_2$ (if $v_1 = v_2$ it is 0). ...
88 views

### First-order methods for solving SDP with geometric convergence or better

Is there any first-order method that can solve general SDP in a geometric (linear) rate? or super-geometric (super-linear) rate?