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.
Yes, but as I said elsewhere, computing the kth bit of a number is a different problem than approximating the number.
-
-
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.
-
Tweet unavailable
-
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.