Podcast 030Revision #4, 11/21/2008 8:42 AMUser: "added at 41 min" Tags: (None) Previous Next |
Podcast 030Revision #5, 11/24/2008 10:31 AMUser: "Added proof that Jeff needs to listen to Joel more" Tags: (None) Previous Next |
---|---|
White: "Truck Nuts for Everyone" was on the top of the list of that forum. Spolsky: Truck Nuts? White: Truck Nuts. Uhh...You're not familiar with Truck Nuts, Joel? They don't have many of those in New York, I imagine. Um... (laughter) Spolsky: Ok, I'm so out of it. I only just found out about that puppy cam last night. That's how behind I am. What is a...what are truck nuts? White: Uhh...they are die-cast brass...balls for your truck. Jeff: Oh, I've seen those. Spolsky: We don't even have trucks in New York City, so... (41:00) Spolsky: OK, I see why you got in trouble here. First of all they are amenable - there are often shortcuts that get you what may not be the best answer but you get something that is pretty darn good. Jeff: Right, right, but again, with the computer you're typically used to getting the best possible answer. The computer gives you -- there's nothing in Excel which gives me a formula which is kind of correct - it's always correct, right? You're doing math so computers are math made circuitry. So I think that's the intriguing thing to me about them. Spolsky: OK.
| White: "Truck Nuts for Everyone" was on the top of the list of that forum. Spolsky: Truck Nuts? White: Truck Nuts. Uhh...You're not familiar with Truck Nuts, Joel? They don't have many of those in New York, I imagine. Um... (laughter) Spolsky: Ok, I'm so out of it. I only just found out about that puppy cam last night. That's how behind I am. What is a...what are truck nuts? White: Uhh...they are die-cast brass...balls for your truck. Jeff: Oh, I've seen those. Spolsky: We don't even have trucks in New York City, so... (38:00) Jeff: ... people really objected to the post that I made to the statement that "nobody really knows what an NP-Complete problem is". And that is technically, the way I said it is kind of wrong. But let me be clear about what my thinking is here. What I was referring to was the NP=P problem, which is. So a little bit of background on this. So NP-Complete basically means nobody has a good algorithm for solving this problem. Spolsky: Other then an exhaustive search and its gonna grow geometrically. Jeff: Yeah it takes forever. Like the only good solution, the smartest people in computer science can come up with is to try every possible solution. Spolsky: ... Jeff: right. right. And the thing I was trying to say poorly is that the reason that we call them NP-Complete is that nobody has proven that they can solve it in polynomial time. In other words nobody has, our brighest minds in computer science, nobody can come up with a better algorithmn then like n factorial or even n cubed, for a lot of times is pretty bad. If n cubed is the best (laugh) solution we can come up with Spolsky: but that's not NP-Complete, that's still not Jeff: yeah, yeah. Spolsky: n cubed is still polynomial. Jeff: yeah, yeah. So what I was really trying to say is that its this weird definition where you just throw a bunch of smart people at it and they will agree yeap this is NP-Complete. And there is nothing saying that another super smart person will not come up and say "you know what I can solve this in n squared" [Proof that Jeff doesn't listen to Joel. And Jeff still doesn't understand NP-Complete] (41:00) Spolsky: OK, I see why you got in trouble here. First of all they are amenable - there are often shortcuts that get you what may not be the best answer but you get something that is pretty darn good. Jeff: Right, right, but again, with the computer you're typically used to getting the best possible answer. The computer gives you -- there's nothing in Excel which gives me a formula which is kind of correct - it's always correct, right? You're doing math so computers are math made circuitry. So I think that's the intriguing thing to me about them. Spolsky: OK.
|