A relevant classical result in complexity theory is: if NP⊆P/poly then the polynomial hierarchy collapses. Which is to say, this is pretty unlikely. This means that you can’t solve SAT in time which is polynomial in the size n of the circuit, even if you had unlimited time to precompute an advice string for the given n that you need.
A relevant classical result in complexity theory is: if NP⊆P/poly then the polynomial hierarchy collapses. Which is to say, this is pretty unlikely. This means that you can’t solve SAT in time which is polynomial in the size n of the circuit, even if you had unlimited time to precompute an advice string for the given n that you need.