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 ...
- 1,156
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 "...
- 1,156
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 ...
- 141
-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²).
- 1
Top 50 recent answers are included