On Sun, Jun 10, 2012 at 9:28 PM, Jim Bromer <[email protected]> wrote: > > I have been looking for a polynomial time solution to Boolean > Satisfiability for some years because I believe that there is a slight > chance that the Lord encouraged me to do so. (It would be a virtual miracle > if I figured it out so I believe that this will constitute outstanding > evidence that the Lord did encourage me.) Of course the Lord may not have > encouraged me and I may have just jumped to a wrong conclusion. > > For a number of years Matt Mahoney has been telling me that if I found a > polynomial time solution to Boolean Satisfiability then I would have a > polynomial time solution to factorization. Because, he explained, I could > simply apply my solution to Satisfiability to a binary multiplication > algorithm and it would be able to find the factors to a given number in > polynomial time. I was skeptical of his claim but I had trouble grasping > what was wrong with it. I would start to see my criticism but I could never > quite get it. However, I now see what is wrong with his theory. > > A multiplication of two numbers can be done in n^2 time if n is the number > of digits in each of the multiplicands. (This may be inaccurate; I am just > trying to give a quick ballpark value.) So, I think Matt reasoned, if my > satisfiability solver worked in n^3 time then it should be able to factor a > binary number in n^5 time. This reasoning is wrong. I can explain this in > intuitive abstract terms that will help you understand, but the way I > discovered the error was by wondering if my latest method (which is still in > its earliest stages) could be used to find prime numbers in polynomial > time. I have absolutely no hard evidence that my method will work but when > I started thinking about Matt’s binary circuit (the binary multiplication > algorithm) I realized I would not be able to get it to work because I would > not be able to use my method on it in the way Matt thought a solver could be > used. So I had to discover how I might go about getting the solver to solve > for factorization using the multiplier algorithm and once I did I quickly > saw the problem clearly for the first time. > > I will explain the problem using intuitive abstract terms to help Matt and > others see why he was wrong. A binary multiplication algorithm is a > deterministic algorithm – when it is used to multiply two given numbers. > But when it is being presented as a method to factorize a given number it is > a non-deterministic method relative to a single pass of the multiplier. In > order to turn it into a deterministic algorithm we would have to encode > every possible multiplication that might produce the given number in the > terms of a Boolean formula and the number of possibilities doubles with each > additional digit of the multiplicands. > > You might narrow the range of possible multiplicands to be tried using the > length of the given number to be factored (relative to the most significant > digit) but you still have to define (the Boolean logic for) every possible > multiplication of all multiplicands within that range. But anyway, Matt’s > binary multiplier algorithm could not be used to find a factor a given > number in polynomial time even given a polynomial time solution to Boolean > Satisfiability because its input length for factorization - when expressed > as a formal Boolean statement - is 2^n X n^2. > > This also shows that there is something different between the relations of > algorithm states and utilization states. If a function is not reversible > than the complexity of using the function as if it was reversible is going > to be different unless the runtime - memory use is equal for running it in > either direction. > > Jim Bromer
You do recall the program I posted. You input an n-bit number X and it outputs a Boolean circuit (expressed as a C program) that multiplies two numbers (n bits each), compares the product to X, and outputs 1 if they match. The Boolean circuit has O(n^2) gates as a Wallace tree and O(n) gates for the comparison circuit, or O(n^2) overall. The circuit is deterministic. As I explained, you do not have to try every possible pair of n-bit numbers. You set one of the 2n inputs to 0 and ask your polynomial solver if there is a satisfying solution among the remaining inputs. If the answer is yes, then you leave it at 0. Otherwise you change it to 1. Then you repeat this process for all 2n inputs. When you are done, the inputs will be set to the factors of X. Assume your SAT solver runs in O(m^k) time for some k, where m is the size of the input. Since the input size to your SAT solver is m = O(n^2) and it has to run 2n = O(n) times, then the time for factoring is O(n^(2k+1)), which is polynomial. So in your example, if SAT is O(m^3), then factoring is O(n^7). -- Matt Mahoney, [email protected] ------------------------------------------- AGI Archives: https://www.listbox.com/member/archive/303/=now RSS Feed: https://www.listbox.com/member/archive/rss/303/21088071-c97d2393 Modify Your Subscription: https://www.listbox.com/member/?member_id=21088071&id_secret=21088071-2484a968 Powered by Listbox: http://www.listbox.com
