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.)
139
questions with no upvoted or accepted answers
15
votes
0
answers
487
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,537
13
votes
0
answers
533
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
12
votes
0
answers
267
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?...
- 231
10
votes
0
answers
177
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 ...
- 652
10
votes
0
answers
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 ...
- 233
10
votes
0
answers
663
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
9
votes
0
answers
159
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?
...
- 307
9
votes
0
answers
630
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
8
votes
0
answers
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
8
votes
0
answers
348
views
Linear space language that requires exponential time without ETH
The $\mathsf{P} \neq \mathsf{PSpace}$ conjecture means that
There is a language $L \in \mathsf{DSpace}(O(n^t))$ for some $t>0$ such that for all positive integers $k$, $L$
requires $\Omega(n^k)...
- 1,318
8
votes
0
answers
177
views
Cell probe model vs transdichotomous ram
can someone explain me the difference between those two (cell probe model and transdichotomous ram)?
In cpm I'm allowed to do computation for free, and complexity of algorithm is just a number of ...
- 81
8
votes
0
answers
1k
views
Is there an ambiguity test for CFGs faster than trying all strings?
It is well known that testing whether a grammar is ambiguous is undecidable. It is however trivially decidable for any $G$ whether $L_n(G) := \{ w | w \in L(G) \wedge |w| \leq n \}$ for any $n \in \...
- 4,670
8
votes
0
answers
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
7
votes
0
answers
171
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
7
votes
0
answers
142
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
7
votes
0
answers
250
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,100
7
votes
0
answers
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 ...
- 171
6
votes
0
answers
82
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
6
votes
0
answers
192
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,451
6
votes
0
answers
237
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$?
6
votes
0
answers
138
views
Evaluating addition chains
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
6
votes
0
answers
205
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
6
votes
0
answers
101
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
6
votes
0
answers
847
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
0
answers
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,001
6
votes
0
answers
247
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
6
votes
1
answer
339
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
5
votes
0
answers
141
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.6k
5
votes
0
answers
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
5
votes
0
answers
319
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
5
votes
0
answers
898
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
5
votes
0
answers
410
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
5
votes
0
answers
855
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
1
answer
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
4
votes
0
answers
95
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,121
4
votes
1
answer
149
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
4
votes
0
answers
289
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 ...
- 149
4
votes
0
answers
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 ...
- 311
4
votes
0
answers
260
views
Is $L\subset NC^1$
Arora and Barak's online book claims in exercise 6.11 that $NC^1=L$. While the $NC^1\subset L$ direction is relatively straightforward and explained in many other texts, I couldn't prove or find the $...
- 643
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
177
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
4
votes
0
answers
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
4
votes
0
answers
327
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
3
votes
0
answers
70
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
3
votes
0
answers
133
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 ...
- 900
3
votes
0
answers
341
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 ...
- 209
3
votes
0
answers
43
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
3
votes
0
answers
95
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,537
3
votes
0
answers
189
views
Is $SUBLOG\subset DTIME(n)$?
In the course of trying to give a more natural answer to a previous question of mine involving the complexity classes $$SUBLOG=\{L\mid L \text{ is recognizable by a sublogarithmic-space TM} \}$$ and $...
- 643