P=NP
Jerry Kuch
>In article <daemon9D...@netcom.com>, Route <dae...@netcom.com> wrote:
>>
>> At least according to the computer animation artists that worked
>> on "The Simpson's Halloween Special"... If anyone saw it, you
>> may or may not have noticed the floating "P=NP" that drifted
>> across the computer-generated landscape...
>
>Yes, and it also had a counterexample to Fermat's Last Theorem
>(it said 1782^12 + 1842^12 = 1922^12). Close but no cigar!
>
>PS, my favorite line was Homer looking around the fancily-rendered
>3-D computer generated landscape and saying "this place looks
>expensive.... I feel like I'm wasting a fortune just standing here!"
I also caught Euler's formula floating by in the background over Homer's
shoulder...
--
Jerry Kuch EMail: gdk...@mercator.math.uwaterloo.ca, NeXTMail welcome.
IMPORTANT NEWS: Scripts for "Godzilla Vs. Desutoroia" had envisaged
the monster's main target as the 1996 World City Expo in Tokyo
but the idea fell through when Gov. Yukio Aoshima cancelled the event.
Hans Moravec
In article <phrDHA...@netcom.com>, p...@netcom.com (Paul Rubin) writes:
>In article <daemon9D...@netcom.com>, Route <dae...@netcom.com> wrote:
>> At least according to the computer animation artists that worked
>> on "The Simpson's Halloween Special"...
>
>(it said 1782^12 + 1842^12 = 1922^12). Close but no cigar!
1782^12 + 1841^12 = 1922^12 is much closer.
-- Hans Moravec CMU Robotics
John Merritt
>
>>I also caught Euler's formula floating by in the background over Homer's
>>shoulder...
the existance of the "hypothetical" 3-rd dimension. Very clever!
I won't spoil it here. I had to watch the show again to understand it.
--
\__ \______ \__ \__ \___ \__
\__ \________ \__ \__ \____ \__
\__ \__ \__ \__ \__ \_____ \__
\__ \__ \__ \_______ \__ \__\__ John.M...@gsfc.nasa.gov
\__ \__ \__ \__ \_______ \__ \____
\__ \__ \__ \__ \__ \__ \__ \___ "Yesterday, I knew nothing.
\________ \_______ \__ \__ \__ \__ Today, I know that."
\______ \_____ \__ \__ \__ \_
Route
| The ascii sequence, written in HEX, floating by Homer explains what laws govern
| the existance of the "hypothetical" 3-rd dimension. Very clever!
| I won't spoil it here. I had to watch the show again to understand it.
How mouch of a spoiler is it now? It's ALL over a.t.s.
It's 'Frink Rules'...
--
----| Infinity / Route / daemon9 |--------|------------------|--------------
--| Founding member: The 0x47 0x75 0x69 0x6C 0x64 | Finger for information |--
[RSADSALUCGARGOYLEIDEADESLUCIFERLOKIFEALSHAMD5HAVALSNERFU]
coming soon... the infonexus.... All of our prayers answered.
Haynes Lee
>
>
> At least according to the computer animation artists that worked
> may or may not have noticed the floating "P=NP" that drifted
> across the computer-generated landscape...
If they are talking about matrix multiplication then "P=NP"
is the steady-state solution reached by multiplying a
square matrix N recursively by another row/column matrix P an infinite
number of times. A steady state solution can be only reached
if there is an eigenvalue at 1 and all others less than 1.
Haynes Lee
l...@hp.rmc.ca
Joel Rubin
I think they are probably refering to computer problems that can be solved in
polynomial time (as a function of the length or size of the input) versus
problems that take more time to solve.
Route
| If they are talking about matrix multiplication then "P=NP"
| is the steady-state solution reached by multiplying a
| square matrix N recursively by another row/column matrix P an infinite
| number of times. A steady state solution can be only reached
| if there is an eigenvalue at 1 and all others less than 1.
I'd rekon they are refering to the age old P!=NP deate in computer
science. Problems in P are solvable in polynomial time on a
deterministic machine, and are deemed tractable, while problems in
NP are solvable in polynomial time (for a decent sized input) only
on a non-deterministic machine, and are deemed intractable. Problems
are deemed intractable for several reasons: They are so complex
that the running time of the solution scales exponentially (or the
solution itself cannot be bound by a polynomial function of the input
length). Some problems are so hard, they are deemed undecidable.
That is, *no* algorithm exists for solving the problem. These
problems are quite intractable...
Hauke Reddmann
--
Hauke Reddmann fc3...@math.uni-hamburg.de
<:-EX8
Robert Israel
|> I'd rekon they are refering to the age old P!=NP deate in computer
|> science. Problems in P are solvable in polynomial time on a
age old = dating back to 1972 or so. Makes me feel like a dinosaur.
|> deterministic machine, and are deemed tractable, while problems in
|> NP are solvable in polynomial time (for a decent sized input) only
************************ ^^^^
No, no, no!
(1) Polynomial time means time bounded by a polynomial in the size of the
input. It only makes sense for a class of problems (rather than a single
problem) as the size of the input -> infinity. So this "for a decent sized
input" is meaningless.
(2) NP means that it _is_ solvable in polynomial time on a non-deterministic
machine (e.g. because if you guess the right answer, you can verify your
guess in polynomial time). It doesn't mean it is _only_ solvable in polynomial
time on such a machine. In particular, P is a subset of NP.
|> on a non-deterministic machine, and are deemed intractable. Problems
|> are deemed intractable for several reasons: They are so complex
|> that the running time of the solution scales exponentially (or the
|> solution itself cannot be bound by a polynomial function of the input
"Intractable" is not a precise concept, but as a rough approximation we might
agree that a class of problems is intractable if it is not in P.
There is, of course, the possibility that the running time is worse than
polynomial but better than exponential, as may be the case for factoring
integers. Is that intractable?
|> length). Some problems are so hard, they are deemed undecidable.
|> That is, *no* algorithm exists for solving the problem. These
|> problems are quite intractable...
Undecidable problems are another subject altogether. Of course they're not
in NP.
--
Robert Israel isr...@math.ubc.ca
Department of Mathematics (604) 822-3629
University of British Columbia fax 822-6074
Vancouver, BC, Canada V6T 1Y4
Joel Rubin
mathematical computer science DOES derive from a Simpson's program--the
people who drew a Simpson's special put up "P=NP" on the screen. They
also put up a not-quite-true counter-example to Fermat's Last Theorem.
No proof, though. I guess they didn't have enough space in the margins
of the film. Is Matt Groening (sp?), the creator of the Simpsons, a
closet nurd?
In article <47nn4b$1...@ixnews6.ix.netcom.com>, john...@ix.netcom.com
says...
>
>In <daemon9D...@netcom.com> dae...@netcom.com (Route) writes:
>>
>>
>
>Tons of annoying Math stuff snipped.
>
>> Fatoring is superpolynomial. And, depending on how you define
>> intractable, sure, for a large enough composite, in can be.
>>
>>| |> length). Some problems are so hard, they are deemed
undecidable.
>>| |> That is, *no* algorithm exists for solving the problem. These
>>| |> problems are quite intractable...
>>
>>| Undecidable problems are another subject altogether. Of course
>they're not
>>| in NP.
>>
>
>Jeez, and I thought this was a Simpsons Newsgroup. I have but one
>thing to say to you two bookworms.
>
>"Take it outside, Mathboys!"
>-In honor of Superintendent Chalmers-
>
>John
>--
>============================================================
>john...@ix.netcom.com "Nightswimming, deserves
> a quiet night."
> -Michael Stipe-
>============================================================