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.
-
-
Replying to @browserdotsys
No, not by finding a polynomial-time algorithm for SAT. Just by using brute-force search.
2 replies 0 retweets 0 likes -
Replying to @browserdotsys
Yes, but as I said elsewhere, computing the kth bit of a number is a different problem than approximating the number.
1 reply 0 retweets 0 likes -
Replying to @browserdotsys
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.
1 reply 0 retweets 0 likes -
Replying to @browserdotsys
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.
1 reply 0 retweets 0 likes
k has log(k) bits, so should express things of size O(log(k)).
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.