# 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.)

118 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
464 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,237
530 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
229 views

### the largest element of a matrix product

Given two matrices, I'm interested in finding the largest element of their product. I wonder if it's possible to do it significantly faster than the matrix multiplication the solution seems to require?...
• 221
253 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 ...
• 233
593 views

### Simple path on dag with backward edges

What is the complexity of the following problem ($\in$ P? NP-hard?): Input: a directed acyclic graph $D=(V,E)$, a set of backward edges $E'\subset V\times V$, and two distinct nodes $s$ and $t$. ...
• 1,085
138 views

### Is 4-in-a-row PSPACE-complete?

This paper by Laurens Kuiper shows that axis-parallel k-in-a-row is PSPACE-complete in complexity for k ≥ 5, but leaves the question open for k = 4. Has there been any research progress on this ...
• 580
154 views

### Time complexity of exponentiating s-sparse matrices

Could someone suggest me a reference which discusses the time complexity of algorithms meant for exponentiating (finding $e^A$ approximately given $A$) s-sparse matrices, along with their error rates? ...
414 views

### Fundamental assumptions in complexity analysis

I am a software engineer and I need a bit of clarification. The practical performance of algorithms is usually compared against models where arithmetic and dereferencing are instantaneous, such as RAM....
• 191
4k views

### Time complexity of a branching-and-bound algorithm

Theoretical computer scientists usually use branch-and-reduce algorithms to find exact solutions. The time complexity of such a branching algorithm is usually analyzed by the method of branching ...
• 854
339 views

• 4,600
257 views

### For median is it optimal to compare in pairs first?

Median can be done in linear time and is now down to (I think) $2.97n$. The lower bounds is (I think) $(2+\epsilon)n$ where $\epsilon$ is very small. The following theorem, if true, may help improve ...
• 549
130 views

### Complexity of solving vs verifying in P

Thinking of (seemingly) very different complexity of finding a solution to a NP problem and verifying it as the basis of practical cryptography, I am wondering if such separation is possible among ...
• 243
248 views

### How quickly can we find an arbitrary digit in multiplication?

In considering an answer to this question, I once again wondered how quickly we could find a digit in multiplication. We may first consider previous results. Finding the least significant digits is ...
• 2,080
265 views

### Complexity of reachability in Markov Chains

Is anything known about the complexity of the following problem beyond membership in PTIME: Given a finite Markov chain $M$, an initial state $q_0$ and a set $F$ of (absorbing) states, is the ...
181 views

### Computing the $n$-th bit of the binary representation of $\pi$

I (only) learned today about the following fact: The $n$-th binary digit of $\pi$ is computable without calculating all the previous digits. This apparently has been discovered in 1995, and follows ...
• 4,331
222 views

### Nondeterminstic Linear Time vs Other Complexity Classes

Is it known whether or not nondeterministic linear time contains $P$ and/or smaller classes such as Uniform-$NC^1$?
132 views

I hope this is a suitable place to ask this question. An addition chain of size $n$ is a sequence $x_1, \dots, x_n$, where $x_1$ is fixed to 1 and $x_i = x_j + x_k$ for some $j,k < i$. I am ...
• 161
157 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) ...
• 580
99 views

### Looking for an easy/pedantic exposition of Renegar's famous result on polynomial optimization

In September $1989$, Renegar had this famous sequence of 3 papers titled, "On the Computational Complexity and Geometry of the First-order Theory of the Reals, Part I/II/III". I was wondering if ...
• 1,443
816 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,...
1k views

### Does L=P imply any new complexity class separations?

If L=P then P is not equal to PSPACE. This follows from PSPACE properly containing L. I am wondering if L=P implies any stronger separation between complexity classes? Does it imply P is properly ...
• 3,993
244 views

### Restricted Reachability Problem

Let $G$ be a directed acyclic graph with $V$ vertices and $E$ edges. Choose some subset of $n\leq V$ "special" vertices $\{v_i\}_{i=1}^n$. How efficiently can we preprocess $(G, \{v_i\})$ so that we ...
• 800
335 views

### Are all problems in the same time hierarchy related to each other?

In this problem, "runtimes" refer to worst-case complexity compared up to constant factor. Say you have two problems, A and B, in the same time hierarchy, and it is clear that algorithm P ...
• 69
140 views

### Program size versus program running time

Short "naive" question: Is it true that faster algorithms require longer programs ? Given a decision problem $A$ and a reasonable model of computation, there can be many ways (algorithms) ...
• 22.3k
169 views

### Complexity of extracting a coefficient of a polynomial in multiple variables

I'm looking for efficient algorithms for problems of the following type: Let's say we have the variables $x_1,...,x_n$. Over these variables, we are given a function $p_1\cdot ... \cdot p_m$, ...
• 151
299 views

### Does Depth-First-Search admit a quasilinear time algorithm in mutitape Turing Machine model?

Depth-First-Search (DFS) has a quasilinear (i.e.,$\widetilde{O}(m+n)$) time algorithm in random access model (RAM). I am curious about whether DFS still admits a $\widetilde{O}(m+n)$ time algorithm in ...
• 51
744 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 ...
• 51
380 views

### Do we know some quasi-polynomial problem that is known to not be in NP?

The title pretty much says it all, but to explain how I got there: I think, that one of the reasons we are unable to prove or disprove , but mainly disprove $P=NP$ (and yes, I was provoked by the ...
• 151
151 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
1k views

### Optimality of Greedy algorithm for minimization Knapsack Problem

Given items with weight $w_i$ and profits $p_i$, minimization Knapsack problem is to pick a subset of items $I$, s.t. $\sum_{i\in{I}}{w_i} \geq W$ and $\sum_{i\in{I}}{p_i}$ is minimized. The greedy ...
• 307
88 views

### Simulating a $k$ tape Turing machine with a 2 tape Turing machine

Let $k$ be an (fixed, $3$ for instance) integer, what is the fastest simulation of a $k$ tape Turing machine by a two tape Turing machine? That is we're looking for the best 2 tape TM $U$, such that ...
• 109
81 views

### Finding a largest symmetrical subset of a k-CNF propositional formula

I have a k-CNF propositional formula $F$ which do not admit any global symmetry i.e. there is no permutation $\sigma$ of its variables such that $\sigma(F) = F$ . I'm interested in finding the largest ...
• 301
188 views

• 560
170 views

### Complexity of a naive algorithm for finding the longest Fibonacci substring

I already posted this question here but I didn't receive an answer, so I'm posting it here as well :) Given two symbols $\text{a}$ and $\text{b}$, let's define the $k$-th Fibonacci string as follows: ...
• 151
749 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,186
185 views

### Complexity of computing logarithm of a prime power

Suppose $n = p^k$ for some prime number $p$ and some non-negative integer $k$. What is (the best-known upper bound on) the complexity of computing $k$ on input $n$ (given in binary)? It is important ...
• 2,251
320 views

### Time complexity for solving linear congruences?

What is the best known algorithm to solve linear congruences of the form below? $$a x + b \equiv 0 \space (n)$$ And what is the time complexity of it?
• 41
126 views

### Graph problems in P with unknown lower bounds

I am looking for references to interesting graph problems, which are known to be in P, but their precise big-O lower bounds are elusive. I would split this into 2 classes: problems, where we know of ...
• 723
135 views

### Fastest known algorithm to enumerate k-cliques in a graph for fixed k

Is the best known algorithm for finding all $k$-cliques in a graph with $n$ nodes, for a fixed $k$, given by https://theory.stanford.edu/~virgi/combclique-ipl-g.pdf ? The time-complexity of the ...
• 189
42 views

### Time complexity of finding a point of infinite order on a rank 1 elliptic curve over Q

As an outsider, it sounds like a lot of progress has been made on understanding rank 1 elliptic curves over Q. Much of the BSD conjecture is known for rank 1, and Heegner points provide a way in ...
• 131
86 views

### Lower bound for reversing a list using queues

How do you prove (or disprove) that a list of length $n$ cannot be reversed in time $o(n \log n)$ using $O(1)$ queues? Each queue is FIFO. Time refers to the number of operations on the queues. ...
• 2,237
353 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 ...
• 1,102
128 views

### How does communication complexity relate to time complexity in distributed algorithms?

Some distributed algorithms (e.g. Bracha broadcast) runs in a constant number of rounds. I'm interested on how you'd analyse the time complexity of such algorithm, especially when the message size ...
• 131
200 views

### Implications of an $\tilde{O}(n^{1.5})$ 3XORSUM algorithm

Assume one had a (randomised or deterministic) algorithm with asymptotic complexity $\tilde{O}(n^{1.5})$ for the problem of finding $x,y,z\in L$ where $L$ is a list with $n$ binary vectors of ...
• 1,986
146 views

### Testing for satisfiability of a system of linear equations over GF(2)

Consider a system linear equations in $x$, $Ax =b$, where A is an $n\times n$ matrix, and $b$ is a column vector, and all operations are over $GF(2)$. Is it easier to check satisfiability of the ...
• 271
81 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?
• 792
Many matrix diagonalization algorithms have time complexity $\mathcal{O}(n^3)$ where $n$ is the number of columns/raws (consider only square matrices). What is the best time lower bound it is known? ...