## Podcast 030

**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"

(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.