Where does this paper prove the middle bullet point of its abstract?
I have looked through that paper fairly thoroughly.
There are three things I want to read how they're getting around.
- Reductions from NP problems to SAT may have the effect
of applying arbitrarily large polynomials to the input size.
Theorems 2 and 3 and 20 restrict the runtime of their learning algorithms.
Theorems 2 and 3 and 20 consider randomized algorithms.