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
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.
1 reply 0 retweets 0 likes -
Replying to @browserdotsys
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.
1 reply 0 retweets 0 likes -
That is correct. Fortunately, it does not grow super-exponentially.
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.