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