The number in [0,1] whose binary expansion is given by the nth bit is 1 iff the nth Boolean formula is satisfiable can be computed in polynomial time.
I don't know what you mean by polytime for ε. But a number is polynomial-time computable if there is an algorithm to approximate it to within 2^-k in poly(k) time, or equivalently to approximate it to within 1/k in poly(log(k)) time.
-
-
k has log(k) bits, so should express things of size O(log(k)).
Thanks. Twitter will use this to make your timeline better. UndoUndo
-
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.