On Tue, Jun 12, 2012 at 9:34 PM, Matt Mahoney <[email protected]>wrote:
> 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] > If the 2 n-bit input numbers are taken as the literals of a Boolean formula, and the output of the multiplier (the product) is compared to the number to be factored (or tested to see if a factor exists) so that it returns a 0 or 1 based on whether it the product matches, and the process of the evaluation of each bit in the factor is made as if it were a sub compound formulas in the formula, then I guess this would have the shape of a viable Boolean formula which could be solved by a SAT solver. You would not need to test a multiplicand against the all of the other possible values of the other multiplicand (which is what I think you were saying) because the solver should be able to find a solution if one exists - as long as the algorithm or circuit were described as a valid Boolean formula. However, I think I did demonstrate that the problem is more difficult than just slapping a solver onto an algorithm. For example, a multiplier algorithm might be able to rely on the operating system to place some data to implicitly into a memory location and this might not be obvious to the solver. This seems like a detail but it shows that a complication of memory location, which is always explicit and superficial in a Turning Machine can be hidden in a modern code. So you would have to look at the run time code in order to know all the details of the program. And the entangling details of moving back and forth on the Turning Machine tape presents an extraordinary complicating factor to writing the program for a solver. The thing is is that memory location is not even typically necessary (or necessarily necessary) for converting an algorithm into a proper Boolean formula. If this is true it shows how important it is to convert an algorithm into a valid Boolean Formula. Another problem, taken from the example of the multiplier, is that since only one solution is called for (in the dogma of the modern SAT solver challenge) you would always get a solution for any number to be tested even if the number is prime. I do not consider this to be a serious problem but it does demonstrate how the problem could become more difficult for slightly more complicated algorithms. I am trying to figure out how one might go about converting an algorithm into a proper Boolean Formula using some kind of formal procedure and I have run into a lot of trouble because the issues can be so subtle. For example, if an algorithm has an internal generator and the number is not considered to be part of the input to the formula (the literals) but it is treated as a sub compound of the formula, then each possible iteration of the generator has to be considered. (Imagine a generator which is stringing together different combinations of input literals from each call to the generator. The generator could actually be creating new sub compounds dynamically, in essence creating a new Boolean Formula for each iteration. So the multiplier looks like it can be converted into a Boolean Formula, but the conversion process is not simple. 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
