New answers tagged

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 ...
Eric Allender's user avatar
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 "...
Eric Allender's user avatar
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 ...
fiktor's user avatar
  • 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²).
Markus's user avatar
  • 1

Top 50 recent answers are included