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

142 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
498 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,577
535 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
282 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?...
• 259
692 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,095
193 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 ...
• 672
264 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
164 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? ...
631 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 ...
• 864
349 views

• 4,720
259 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
115 views

### Parameterized complexity of factoring

When multiplying integer numbers $A$ and $B$, one can use a 0-1 matrix to represent one of the multiplication steps. For example, given numbers (written in binary) $A=1101$ and $B=1011$ the matrix is: ...
• 355
209 views

### Baker–Gill–Solovay Theorem: why $2^n/10$ steps?

Context I'm teaching an introductory complexity theory course right now and although I work in adjacent areas, I'm not an expert on complexity theory myself, so I'm still in the process of working ...
• 273
147 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
251 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,110
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 ...
• 4,041
271 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 ...
97 views

### Time hierarchy for one-tape Turing machines

The time hierarchy for multitape Turing machines is tight (see [1]): if $f(n)=o(g(n))$ and $f,g$ are well-behaved, then $\textrm{DTIME}(f(n))\subsetneq \textrm{DTIME}(g(n))$. However, for one-tape ...
• 303
201 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,481
249 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$?
138 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
223 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) ...
• 672
102 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,453
859 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,...
919 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,226
248 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
344 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
144 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) ...
171 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
320 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
959 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
419 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
185 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
108 views

### $\log^\star n$ is somewhat common in runtimes. Does the superroot ever make an appearance?

Many algorithms and data structures have iterated logarithms ($\log^\star n$) in their runtimes. This function is the discrete inverse of tetration, in that $$\log_a^\star (a \uparrow \uparrow b) = b$$...
• 2,252
205 views

### What is the time complexity of fermionic Fourier transform?

Suppose $N = 2^L$ and we are interested in performing the following transformation a $\mapsto$ a_hat on arrays of $N$ complex ...
• 141
457 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 ...
• 321
83 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 ...
• 321
292 views

• 548
181 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
187 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,281
330 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
371 views

### How do you achieve linear time complexity of greedy graph coloring?

In most resources I could find, greedy algorithm is described as follows: for every vertex $v$, assign the minimal color not used by its neighbors. The above could be implemented as: ...
92 views

### What's the complexity of the "decision version" of counting the paths in a graph?

I learned that "counting the simple paths in a graph(whether directed or not)" is #P-Complete. I'm wondering what the complexity is for its decision version. Here are two types I'm ...
83 views

### Time complexity of context-free languages

I am reading an old paper [1] about time complexity of context-free languages. The computational model is the standard one-tape Turing machine. It is written on page 377 without a proof that "we ...
• 303
136 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 ...
• 920
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 ...