New answers tagged time-complexity
5
votes
Fast algorithms for time bounded Kolmogorov complexity
No faster algorithm is known for computing $Kt(x)$ than the brute-force algorithm. In fact, since the (average-case) complexity of computing $Kt(x)$ is closely tied to the existence of one-way ...
3
votes
is SUBEXP contained within PSPACE?, NP?
SUBEXP is neither known or widely believed to lie in PSPACE (and -- contrary to one of the comments -- this is not known to have any connection to SETH). It is not known whether the containment "...
0
votes
What is the time complexity of fermionic Fourier transform?
It is at most $O(2^L L^2)$
openfermion.circuits.ffft implements the fermionic Fourier transform on a gate quantum computer. One can simulate this algorithm on a classical computer at the ...
-2
votes
Complexity of greedy coloring
For me it got easier to understand once I explained to myself that for a fully connected graph m = n*(n-1)/2. I.e. in the worst case O(n+m) converges to O(n²).
Top 50 recent answers are included
Related Tags
time-complexity × 389cc.complexity-theory × 144
ds.algorithms × 90
complexity-classes × 40
reference-request × 31
graph-algorithms × 27
lower-bounds × 22
space-complexity × 20
polynomial-time × 19
turing-machines × 18
graph-theory × 17
optimization × 14
ds.data-structures × 14
linear-algebra × 14
sat × 13
time-hierarchy × 13
np-hardness × 12
matrices × 12
sorting × 11
nt.number-theory × 10
quantum-computing × 9
p-vs-np × 9
nondeterminism × 9
approximation-algorithms × 8
fl.formal-languages × 8