Comment

Comment by calf

The technical result has nothing to do with "efficient" which according to textbook CS theory roughly defines it to be the set P, the strictly polynomial time algorithms. Has nothing to do with the ETH result which is still an exponential, 2^(n/ log n), just not a pure exponential.

I'm also confused what you are saying down here. Though I can see how "sub-exponential" is easily misleading terminology.

parent calf 4 days ago

Discussion

Live from the official Hacker News API

A modern reader for Hacker News · SvelteKit + Skeleton