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
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
-1
votes
1
answer
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 ...
- 111
7
votes
1
answer
437
views
Formalization of proofs and computational complexity paradox?
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_{...
- 22.6k
4
votes
1
answer
123
views
Fast Finding Main Diagonal of Matrix Multiplication
Suppose we have two matrices $A_{m\times n}$ and $B_{m\times m}$. Such that $B$ is a symmetric positive definite matrix. Is it possible to compute main diganoal of $A^TBA$ in $O(n\times m)$?
- 189
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
4
votes
0
answers
250
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
0
votes
1
answer
158
views
Reduction from SAT to binary matrix subset problem
I'm trying to understand the answer by @Denis on this question, where he showed a way to reduce from SAT to the binary matrix column subset selection problem. The reason I'm having to post a new ...
- 115
7
votes
2
answers
384
views
Are space and time hierarchies even comparable?
I am wondering if there are any results to what extent the space and time hierarchies "disagree" on which problem is harder. For example, is it known whether there are languages $L_1$ and $L_2$ such ...
- 643
7
votes
2
answers
375
views
Reference Request: complexity results on finding $(1+\epsilon) \log n$ size clique in $G(n,1/2)$
I am trying to find results on the best known time complexity for finding $(1+\epsilon) \log n$ sized cliques in $G(n,1/2)$. More general results would be great, i.e. if $C_p$ is the constant such ...
- 203
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
7
votes
2
answers
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 ...
- 548
7
votes
1
answer
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, ...
- 548
1
vote
2
answers
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 ...
- 548
5
votes
0
answers
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 ...
- 51
3
votes
1
answer
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. ...
- 383
7
votes
1
answer
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 ...
- 101
4
votes
2
answers
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 ...
user47137
3
votes
0
answers
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 ...
- 1,132
6
votes
1
answer
307
views
Quantum polynomial hierarchy vs counting hierarchy
First of all, I'm kinda surprised that I couldn't find any paper/article defining such hierarchy.
It can be defined as follows:
$\Delta_0^{\mathsf{BQP}}=\Sigma_0^{\mathsf{BQP}}=\Pi_0^{\mathsf{BQP}}=\...
- 245
-1
votes
1
answer
250
views
polylogarithmic space [closed]
I apologize if this is a silly question, but could someone tell me whether the class polyL (polylogarithmic space) is equal to the class ATIME(polylog)? If so, where can I find a reference to this or ...
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+ε})$ ...
- 2,537
1
vote
0
answers
147
views
Time complexity of polynomial regression with random coefficients
Suppose that I have
$$\lim_{k,l,m \rightarrow \infty}(f(x,l) ~~=~~ \sum_{n=1}^{m} g(a_{n,k})h(x,n)$$
where the $a_{n,k}$ are pseudo-random real numbers with $k$ digits generated in an arbitrary way, ...
- 11
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
6
votes
0
answers
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) ...
- 652
0
votes
1
answer
352
views
${\bf NP} \not = {\bf E}$ and ${\bf PSPACE} \not = {\bf E}$
We know that ${\bf NP} \subseteq {\bf PH} \subseteq {\bf PSPACE}$.
We also know that ${\bf E} \subset {\bf EXP}$, where
${\bf E} = \cup_c DTIME[2^{cn}]$ and
${\bf EXP} = \cup_c DTIME[2^{n^c}]$.
It ...
3
votes
0
answers
142
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
0
votes
1
answer
102
views
Complexity status of restricted k-clique [closed]
Restricted $k$-clique:
Input: $(G,v,k)$ where $v$ is vertex in $V$
Output: k-clique containing vertex $v$.
What is the space and time complexity status of this Restricted $k$-clique problem?
Is ...
- 175
10
votes
1
answer
784
views
Comparing two products of lists of integers?
Suppose I have two lists of positive integers of bounded manitude, and I take the product of all elements of each list. What's the best way to determine which product is larger?
Of course I can ...
- 213
2
votes
2
answers
81
views
Maximal non-reducible vertex cover of a graph
Let $G=(V,E)$ be a graph (i.e. an undirected simple finite graph).
We say that a vertex cover $V'$ of $G$ is non-reducible if any $V''$ with $V''\subsetneq V'$ is not a vertex cover of $G$. We say ...
- 21
18
votes
2
answers
2k
views
"Almost sorting" integers in linear time
I am interested in sorting an array of positive integer values $L = v_1, \ldots, v_n$ in linear time (in the RAM model with uniform cost measure, i.e., integers can have up to logarithmic size but ...
- 8,896
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
4
votes
1
answer
579
views
What is the time complexity of computing a Fibonacci number of at least n?
This is not the same as that classic time complexity problem about Fibonacci numbers your professor taught you in school. (That one asked for the time complexity of the nth Fibonacci number; I'd like ...
- 141
-2
votes
1
answer
262
views
questions on implications Babais quasi P time graph isomorphism result
Babai has reputedly repaired his proof of graph isomorphism in quasipolynomial time.[1] the proof hinges crucially on Johnson graphs.
based on the proof, does this mean now that if Johnson graphs can ...
- 11k
11
votes
1
answer
1k
views
2-NEXPTIME-complete problems
We have a problem and we found an algorithm that appear to be 2-nexptime.
I would like to find known 2-nexptime-complete problems in order to find a lower bound.
I found in literature mainly two ...
- 351
3
votes
0
answers
203
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 ...
- 2,070
16
votes
0
answers
216
views
What is the background in algebraic geometry and representation theory needed for geometric complexity theory? [duplicate]
I'm a mathematics student in my junior year and I'm interested in computational complexity and specially geometric complexity theory. I'm going to learn algebraic geometry and representation theory ...
- 269
8
votes
1
answer
338
views
Succinct complete problems in DTIME(EXP(EXP(...)))
I understand complete problems for $EXPTIME$ or $NEXPTIME$ formulated as succinct instances of e.g. $NP$-complete problems such as $3-SAT$. On input $x$, one efficiently computes a circuit $R(x)$ such ...
1
vote
0
answers
2k
views
Fastest Algorithm for the Minimum Edge Covering Problem
Given an undirected weighted graph, G, where all the weights are non-zero positive numbers, my algorithm must produce a sub-graph G' that satisfies the following constraints:
G' must include all the ...
- 111
4
votes
1
answer
2k
views
Definition of near-linear algorithm
There are quite a lot papers describing near-linear algorithms. They are usually iterative, with linear complexity of one iteration. Others have $O(n\log^k n)$ time compexity.
I'm failed to find a ...
- 141
3
votes
0
answers
147
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
6
votes
1
answer
303
views
Complexity of #SAT for monotone DNF formulae whose hypergraph is a hypertree
A monotone DNF on variables $x_1, \ldots, x_n$ is a disjunction of clauses, each clause being a conjunction of some of the $x_1, \ldots, x_n$. The #SAT problem asks, given a monotone DNF $\Phi$, how ...
- 8,896
2
votes
1
answer
533
views
maximizing inner product
Given two lists $L,L'\subseteq\mathbb{R}^d$ of $n$ vectors each,
how fast can we compute for all $p\in L$ the vector of $L'$ that maximizes the inner product with $p$, i.e., $\arg\max_{p'\in L'} \...
- 1,085
1
vote
0
answers
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 ...
- 916
1
vote
0
answers
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 ...
- 111
-4
votes
1
answer
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?
- 11
2
votes
1
answer
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). ...
- 123
3
votes
0
answers
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?
- 832
5
votes
2
answers
245
views
Popular average-case complexity assumptions
Except for planted clique and random 3SAT, what are the other commonly used average-case complexity assumptions?
- 832
0
votes
1
answer
211
views
How can I find tight asymptotic bounds for this half-history recurrence relation?
The recurrence relation $\forall n\in\mathbb{N}\cup\{0\}$ is $T(n)=\Theta(n^2)+2\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}{T(i)}$, with base case of $T(0)=0$.
Fairly simple tree analysis shows that $T(n)\...
- 119
8
votes
1
answer
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 ...
- 5,127