Fine-grained and exponential-time complexity

Exact running times of hard problems beyond the polynomial/non-polynomial divide: exponential, subexponential and quasipolynomial algorithms for NP-hard or NP-intermediate problems, such as the tensor-network 2^o(n)-time algorithm for 3-SAT and Babai's quasipolynomial-time graph isomorphism theorem, and the exponential time hypothesis.

• Graph isomorphism in quasipolynomial time
• Tensor-network contraction

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.