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.
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.
-
-
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 -
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.