5
The best algorithm for 3-SAT now has numerical upper bound O(1.306995^n).
It is described in this paper:
Thomas Dueholm Hansen, Haim Kaplan, Or Zamir, Uri Zwick, Faster k-SAT algorithms using biased-PPSZ , 2019
Simply speaking, it adds bias to the PPSZ algorithm to let some literals have a higher, lower or equal probability to turn to some value.
In the ...
2
One approach is to implement an interpreter for the RAM model, and then instrument the interpreter with a counter that keeps track of the number of instructions executed. I suspect it should be possible to build an interpreter that incurs at most a $O(1)$-factor slowdown, but I haven't checked the details (the instruction set is so primitive that the ...
Only top voted, non community-wiki answers of a minimum length are eligible
