@Steve W
I’m not a native Enlish speaker, but I thought it looked OK…
http://en.wiktionary.org/wiki/defining_characteristic
Yeah, but 7 mixed fruit is not a realistic order with just 3 people sitting at the table.
Valid AND practical, is my solution. 1 appetiser each plus the sampler plate for everyone to pick from.
In fact, I defy you to find a better solution. Maybe I can’t prove mine is the optimal solution, but my gut tells me it is.
The defining characteristic of an NP-complete problem is that optimal solutions, using math and logic as we currently understand them, are effectively impossible.
No it’s not. That’s the defining characteristic of non-polynomial time algorithms (Hell, practically speaking, even poly-time algorithms much higher than n^2 are out of our league for large N, but we’ll brush that under the carpet).
People seem to treat NP as some kind of synonym for “hard”, but what distinguishes NP from other non-polytime algorithms is not how hard they are, but how easy. Or rather how easy it is to check an answer, rather than find it. If you could run every possible guess in paralell, or just happened to pick the right answer first time, you would run in only polynomial time.
Don’t why, it reminded me of the sitcom named ‘The Big Bang Theory’
sigh It’s articles like this that make people believe that NP means “anything hard” or “unsolvable”. NP stands for non-deterministic polynomial time. That means that if anywhere in the algorithm that requires a decision, you can simultaneously follow both paths, the algorithm will find a solution in polynomial time. Math and logic don’t really enter into, you simply have to explore an answer space that grows exponentially with problem size. If a problem is NP-complete, there is a provable solution, it just takes exponential time.
NP isn’t all hard problems either. If you invented a non-deterministic computer, you could solve NP problems in polynomial time, but there is a class of problems above NP that would still take exponential time. If you find a way to solve those problems quickly, there is yet another class above that, etc. forever.
NP != “hard”
The New Girl should be forced to wear a “Scarlet P=NP” for her sins.
I’ll go to lunch with you Dave, 7 rounds of mixed fruit people sounds like it will end in misery and despair. The point of Chotchkies is to express yourself - don’t forget the flair!
Dave Hemming:
For this small of N, you can calculate all solutions quickly. I did. There are just two solutions. Yours and Alex’s. May your gut be satisfied 
Hey, Jeff, thanks for the link! I’ll be at StackOverflow Toronto, so if you need any accordion assistance (perhaps to play off speakers “Keyboard Cat” style), just let me know!
What can I say, it’s a crazy world out there, whether you’re coding or dating. Just keep your chin up, you wits about you, your accordion tuned, write unit tests and use a condom.
Wow. Jeff just can’t resist the NP discussion. It is like watching a train wreck. He is like a moth drawn to a flame.
Jeff: please, stop trying to be a computer scientist, or at least stop trying to explain things you don’t understand.
As other already pointed out, the sentence
“The defining characteristic of an NP-complete problem is that optimal solutions, using math and logic as we currently understand them, are effectively impossible.”
is obviously wrong.
First, problems in NP are computable, so optimal solutions are possible (of course, assuming NP!=P we need to wait long for them).
For small problem instances it’s not a problem even on desktop PCs.
Then, this “definition” does not define the class of NP-complete problems, because anything harder than NPC would still fall under the same description.
And it would be enough to look up Wikipedia to have a simple, understandable explanation:
— Wikipedia—
In computational complexity theory, the complexity class NP-complete (abbreviated NP-C or NPC, NP standing for Nondeterministic Polynomial time) is a class of problems having two properties:
-
Any given solution to the problem can be verified quickly (in polynomial time); the set of problems with this property is called NP.
-
If the problem can be solved quickly (in polynomial time), then so can every problem in NP.
— Wikipedia —
I don’t understand the point of writing a post about something the author cannot explain properly…
Ah, but attendance at UBC implies exposure to atmospheric hallucinogens in much the same way as attendance at Queen’s (the engineering department, at least) implies exposure to Gentian violet and at least one visit to the Blue Toucan. I’m sure NG believed she had actually proved P = NP, and that her work was likely confirmed by a sasquatch and a killer whale.
The post reminds me of my stupid instructor at the college several months ago. He was talking about P, NP problems and he said some wrong statement that from it you could directly prove that P != NP. I told him what. Are you sure!? He said wait, I’ll talk more on that. I said no, it’s wrong… He stopped me and said, I’ll talk in a minute and you’ll understand!!! I said, hey, forget computer science and algorithms for a minute. Just stick to set theory, and proved that if what he said was true, then P != NP, so go and grab your million $ prize. He had nothing to say at the moment and finally agreed he was wrong… Someone helps me out of this stupid college 
Jeff, I think putting UBC and Computer Engineering w/o providing the actual context (that she didn’t go there) other than the link in which people may not click, depicted the school and the department as a failed institution. That’s a bit unfair.
The xkcd mouseover doesn’t work
Heuristic for dating (or how to find a keeper): Date 12 different people at least 3 times each. Make notes on each. Likes, dislikes, points of agreement and friction.
Then go on to new people, and stick with the next one you find that is better than any of the first 12. That’s the Keeper.
Ok, I didn’t follow that algorithm; I just lucked out.
A famous NP-Complete problem is the one Isaac Asimov presents in his “Foundation” Science-fiction series of novels. The main character tries to find the mathematical expression that defines the behavior of the humanity in order to predict the future. To do that, he would have to study all the societies in the galaxy. Of course that it could take a lot of time, and by the time he get close to the goal, some other societies have already arose or changed.
He compares it to try to shake hands with every living person. It is theoretically possible, but while you are trying, more people are born faster than you can shake hands to everybody.
Ted: it it obvious from the excerpt that she didn’t study computer science anywhere. Nothing unfair there.
Why did you write this article? What was your purpose? Seriously. Who is your target audience? Dude seriously buy a book and read it rather than ranting about it.