On Thu, Jun 14, 2012 at 11:17 AM, Jim Bromer <[email protected]> wrote: ... > 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.
It's just a Boolean expression input to your SAT 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 multiplier uses a Wallace tree. It doesn't use a tape. > 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. If X were prime, then the SAT solver would find 1 and X as factors. You would need to add some logic to test for these inputs and exclude them so that the SAT solver would say "no" even with all inputs free. But this does not increase the complexity of the multiplier beyond O(n^2) because the comparisons with 1 and X are both O(n). If X is prime, then your SAT solver would say there is no solution, of course. But you are given that X is composite. In any case, you can run 1 more test and it would not increase the complexity of the problem. -- 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
