An NP-complete problem is a problem for which there's no known polynomial-time algorithm to solve it. (Simplifying a bit here, partially because the last time I really looked at this stuff was about a year ago, and I don't remember all of it.) A problem that can be solved in polynomial time would be something where, if there are n variables, then the problem can be solved in n^x steps, for some fixed value of x. If a problem is NP-complete, on the other hand, the number of steps required increases more quickly than that. The classic example of an NP-complete problem is the traveling salesman problem: you've got a bunch of cities, and you know the distances between each pair of them, and you want to figure out how to travel to all the cities while going the shortest distance. The brute-force way to solve it is to just look at all the possible orders you can travel the cites, calculate the distances for each one, and check which one is the smallest distance. That makes n! different paths to check if there are n cities, which is more than polynomial time. There isn't a known way to improve significantly on that to get it down to polynomial time.
(Sorry, this is kind of sketchy. I thought I understood this stuff, then a class I took last year convinced me I didn't understand it and taught me what all of this actually meant, which was way more complicated than I'd originally thought, and I've forgotten a bunch of it since then.)
Ah, that's what I thought....
The comic did mention the "traveling salesman" problem, right?
The comic did mention the "traveling salesman" problem, right?
Yep, when the waiter has to get away to get to all the other tables. In the shortest possible amount of time.
One of my officemates has this one on her wall: [link]
I got the basic idea based on what you said - and I had he idea from the cartoon. I think it is one of those things that Has a name that I would have guessed there was no name.
One of my officemates has this one on her wall: [link]
Yeah, that's a good one....
Meanwhile, my puppy is sleeping blissfully in front of the radiator, having had a most wonderful visit with bonny and Bart this morning. bonny is a wonderful hostess and Bartleby, like the gentledog that he is, shared all his toys.
Sparky, it was so nice having the two of you, and Bartleby thought very highly of your pup. She is, of course, DEDLEE cute. Even more so in person than in her redonk photos. And that romp around the roses did him in. He was asleep seconds after climbing the stairs.
Bartleby wishes me to report that he will never be the same after consuming your very thoughtful gift. That tendon took him an entire half hour to chew through! An all time record. We are going to have to get some of those.
I was so appreciative that you made the effort to drive into town. And I feel like a TERRIBLE hostess. I was so tired...and when you left, I came home and struck my forehead. FOOD. There was no food! I'm so sorry for my weak showing. I promise to make up for it...especially if you come tomorrow night!
I'm having a dark day. I hate dark days.
Wow. I killed the thread with my melancholy.
Just got back from dinner. Am STUFFED. Again. How come restaurants can't serve reasonable portions? I even had a half salad... Lunch had been ridiculous in size.
Food coma.
