Podcast 030
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"
(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.
