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.
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
-
That is correct. Fortunately, it does not grow super-exponentially.
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.