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.
Correct. But any reasonable definition of polynomial time computable real number should allow for the possibility that polynomial time computable irrational numbers exist, so demanding that the first k bits be computed in poly(log(k)) is unreasonable.
-
-
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.
-
Tweet unavailable
-
k has log(k) bits, so should express things of size O(log(k)).
End of conversation
New conversation -
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.