[Does PCE imply a "universal problem space?"] - A New Kind of Science: The NKS ForumA New Kind of Science: The NKS Forum
Pages:1
Does PCE imply a "universal problem space?"
(Click here to view the original thread with full colors/images)
Posted by: Philip Ronald Dutton
PCE seems to imply the possibility of what might be loosly termed a universal problem space. If all these universal "computation" devices (automatons) can achieve a maximum computation ability then it seems also likely that there is a universal problem space. We have already seen how NP-Complete problems basically can all be mapped to each other. The problem spaces are pretty much the same. (with hindsight, it seems that results from mapping NP-Complete problems would have been a hint of PCE's implications for problem space).
Does the NKS book's PCE chapter discuss PCE in terms of the problem space (I am only half way through that chapter)? What is gained when viewing PCE from the perspective of the data and not the computation devices? What does PCE say about "it's" problem space(s)?
Posted by: Jason Cawley
I recommend the section of the NKS book entitled "Undecidability and Intractability" starting on page 753 and running to page 771, and the accompanying notes, especially those from 1142 to 1147. FWIW...
Forum Sponsored by Wolfram Research
© 2004-2009 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. |
Disclaimer
vB Easy Archive Final - Created by Xenon and modified/released by SkuZZy from the Job Openings