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.

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.