Much as I would like to see a Hawking biography it is hardly blockbuster material. I wanted to see a biography of John Nash, but "A Beautiful Mind" was so fictionalized, that it was a huge disappointment. BoxOffice-wise it was a great movie, but Biography-wise 'twas heavily rewritten. I hear the book "aBM" was based on has things right, but haven't gotten my hands on it yet.
Re:Ford and Fulkerson
on
Does P = NP?
·
· Score: 1
Well it is not a paper, but a book on the subject of "Flows and networks". Out of print.
ISBN:0691079625
I remember there were a bunch of neat books mentioned in some CS-Theory class. All of them were out of print...
Re: Is this problem NP complete?
on
Does P = NP?
·
· Score: 2
Some years ago Cook showed how ANY problem in NP can be reduced to SAT. SAT is the problem to show if for a given boolean formula there is an assignment of values to the variables in it which makes the formula true.
For the gory details see chapter 7 of
Michael Sipser "Introduction to the Theory of Computation" (PWS, Boston 1997)
Well the thing about NP-complete problems is this: some years ago Cook proved that if you take ANY NP problem there is a Polynomial-time procedure which can convert it to one specific NP problem.
Later it was shown for quite a few NP problems that this specific problem can be reduced to them.
Thus a prpblem which is NP-complete is one for which we know that there is a Poly.time procedure which reduces a NP-Complete problem to it (And therefore ANY problem in NP is reducable to it in poly-time.)
So for a problem to be classified NP-Complete you have to reduce a known NP-Complete problem to it in poly-time. So
1) misgrouping one of those wouldn't be easy. and
B) even if it was in P to begin with and someone has reduced an NP-Complete to it, that still shows that P=NP.
Which among other things shows that strong crypto is as bad as weak crypto....
Yes. Which is why in the third ed. of D.E.Knuth's "The art of Computer Programming" it has been degraded to a level of 45 instead of 50. the references given in TAOCP are - A. Wiles, Annals of Mathematics 141 (1995), 443-551 - P. Ribenboim, "13 Lectures on Fermat's Last Theorem"(NY, Springer, 1979) - W.J.LeVeque, "Topics in Number Theory 2" (reading, mass. addison-wesley, 1956), Chapter 3
I seem to recall Wiles being credited with the proof.
I saw it at 0am on Friday. Later on in the afternoon I heard on accessholywood that by now the movie had made $6Mill. and it only cost $25000. And all that before it was released nationwide. On only 31 screens. Which would explain why we got there at 23:40 on thursday and had trouble getting seats...
Anyway on saturday nine of us went camping. On sunday six of us had breakfast for by that time the rest were gone... creepy!!!
OK, they know a little... However another entry in their list (#7) is Ronald Rivest. According to their blurb: "Also known as "chaffing and winnowing," RSA's method has been called the final answer on cryptography"
What has 'chaffing and winnowing' to do with RSA? Or did I miss something? Or do they not believe that someone can have two great ideas?
Slashdot Mirror
Much as I would like to see a Hawking biography it is hardly blockbuster material.
I wanted to see a biography of John Nash, but "A Beautiful Mind" was so fictionalized, that it was a huge disappointment. BoxOffice-wise it was a great movie, but Biography-wise 'twas heavily rewritten. I hear the book "aBM" was based on has things right, but haven't gotten my hands on it yet.
Well it is not a paper, but a book on the subject of "Flows and networks". Out of print.
ISBN:0691079625
I remember there were a bunch of neat books mentioned in some CS-Theory class. All of them were out of print...
Some years ago Cook showed how ANY problem in NP can be reduced to SAT. SAT is the problem to show if for a given boolean formula there is an assignment of values to the variables in it which makes the formula true.
For the gory details see chapter 7 of
Michael Sipser "Introduction to the Theory of Computation" (PWS, Boston 1997)
Well the thing about NP-complete problems is this: some years ago Cook proved that if you take ANY NP problem there is a Polynomial-time procedure which can convert it to one specific NP problem.
Later it was shown for quite a few NP problems that this specific problem can be reduced to them.
Thus a prpblem which is NP-complete is one for which we know that there is a Poly.time procedure which reduces a NP-Complete problem to it (And therefore ANY problem in NP is reducable to it in poly-time.)
So for a problem to be classified NP-Complete you have to reduce a known NP-Complete problem to it in poly-time. So
1) misgrouping one of those wouldn't be easy. and
B) even if it was in P to begin with and someone has reduced an NP-Complete to it, that still shows that P=NP.
Which among other things shows that strong crypto is as bad as weak crypto....
http://www.pe.net/~bidstrup/phone.htm
it wasn't written for gamasutra.
The sidebar says
This article is an excerpt
from After the Gold
Rush, published by
Microsoft Press.
I guess they figured out a way to make ppl
read this drivel without buying the dead tree
thing.
> ummm....fermat's last theorem has been proven.
Yes.
Which is why in the third ed. of D.E.Knuth's
"The art of Computer Programming"
it has been degraded to a level of 45 instead of
50.
the references given in TAOCP are
- A. Wiles, Annals of Mathematics 141 (1995), 443-551
- P. Ribenboim, "13 Lectures on Fermat's Last
Theorem"(NY, Springer, 1979)
- W.J.LeVeque, "Topics in Number Theory 2"
(reading, mass. addison-wesley, 1956), Chapter 3
I seem to recall Wiles being credited with the proof.
I saw it at 0am on Friday.
Later on in the afternoon I heard on accessholywood that by now the movie had made $6Mill. and it only cost $25000. And all that before it was released nationwide. On only 31 screens.
Which would explain why we got there at 23:40 on thursday and had trouble getting seats...
Anyway on saturday nine of us went camping. On sunday six of us had breakfast for by that time the rest were gone... creepy!!!
B.
OK, they know a little...
However another entry in their list (#7) is
Ronald Rivest. According to their blurb:
"Also known as "chaffing and winnowing," RSA's method has been called the final answer on cryptography"
What has 'chaffing and winnowing' to do with RSA? Or did I miss something? Or do they not believe that someone can have two great ideas?