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.
No, not by finding a polynomial-time algorithm for SAT. Just by using brute-force search.
-
-
I'm making the same assumptions about the ordering that people always make when they say SAT is NP-complete. Computing the nth bit of a number is not the same as computing a rational approximation to that number.
-
Tweet unavailable
-
Knowing the nth bit of a real number is typically useless if you do not also know the first n-1 bits. The algorithm I had in mind was to compute the bits 1 at a time by brute-force search until you find enough bits to come within the desired precision.
-
Tweet unavailable
-
Tweet unavailable
-
That is correct. Fortunately, it does not grow super-exponentially.
End of conversation
New conversation -
-
-
Yes, but as I said elsewhere, computing the kth bit of a number is a different problem than approximating the number.
-
Tweet unavailable
-
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)).
- 2 more replies
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.