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
