“I’ll try. ETH claims 3SAT cannot be solved in 1.000...”
Ryan Williams @rrwilliams.bsky.social @rrwilliamsX
Archived text
I’ll try. ETH claims 3SAT cannot be solved in 1.000... 01^n time for some number of zeroes. They claim ETH is false, giving an algorithm that is “sub-exponential” time for 3SAT. That would be surprisingly faster than brute force, the 2^n time.
Quoting @sughanthans1: @rrwilliams thanks for the post ryan.
i know you might be under immense work load but
could you explain to someone who is reasonably intelligent but have not researched this field - what are the implications of these findings?