On Monday, December 30, 2002, at 01:18 PM, Jesse Mazer wrote:
Hal Finney wrote:
One correction, there are no known problems which take exponential time but which can be checked in polynomial time. If such a problem could be found it would prove that P != NP, one of the greatest unsolved problems in computability theory.
Whoops, I've heard of the P=NP problem but I guess I was confused about what it meant. But there are some problems where candidate solutions can be checked much faster than new solutions can be generated, no? If you want to know whether a number can be factorized it's easy to check candidate factors, for example, although if the answer is that it cannot be factorized because the number is prime I guess there'd be no fast way to check if that answer is correct.
Factoring is not known to be in NP (the so-called "NP-complete" class of problems...solve on in P time and you've solved them all!). The example I favor is the Hamiltonian cycle/circuit problem: find a path through a set of linked nodes (cities) which passes through each node once and only once. All of the known solutions to an arbitrary Hamiltonian cycle problem are exponential in time (in number of nodes). For example, for 5 cities there are at most 120 possible paths, so this is an easy one. But for 50 cities there are as many as 49!/2 possible paths (how many, exactly, depends on the links between the cities, with not every city having all possible links to other cities). For a mere 100 cities, the number of routes to consider is larger than the number of particles we believe to be in the universe. However, saying "known solutions" is not the same thing as "we have proved that it takes exponential time." For all we know, now, in 2002, there are solutions not requiring exponential time (in # of cities).
This is also somewhat relevant to "theories of everything" since we might want to ask if somewhere in the set of "all possible universes" there exists one where time travel is possible and computing power increases without bound. If the answer is yes, that might suggest that any TOE based on "all possible computations" is too small to accomodate a really general notion of all possible universes.
And this general line of reasoning leads to a Many Worlds Version of the Fermi Paradox: Why aren't they here? The reason I lean toward the "shut up and calculate" or "for all practical purposes" interpretation of quantum mechanics is embodied in the above argument. IF the MWI universe branchings are at all communicatable-with, that is, at least _some_ of those universes would have very, very large amounts of power, computer power, numbers of people, etc. And some of them, if it were possible, would have communicated with us, colonized us, visited us, etc. This is a variant of the Fermi Paradox raised to a very high power. My conclusion is that the worlds of the MWI are not much different from Lewis' "worlds with unicorns"--possibly extant, but unreachable, and hence, operationally, no different from a single universe model. (I don't believe, necessarily, in certain forms of the Copenhagen Interpretation, especially anything about signals propagating instantaneously, just the "quantum mechanics is about measurables" ground truth of what we see, what has never failed us, what the mathematics tells us and what is experimentally verified. Whether there "really are" (in the modal realism sense of Lewis) other worlds is neither here nor there. Naturally, I would be thrilled to see evidence, or to conclude myself from deeper principles, that other worlds have more than linguistic existence.) --Tim May (.sig for Everything list background) Corralitos, CA. Born in 1951. Retired from Intel in 1986. Current main interest: category and topos theory, math, quantum reality, cosmology. Background: physics, Intel, crypto, Cypherpunks