What is an NP problem? Does this refer to a specific kind of logic problem?
Asked by
2davidc8 (
10189
)
April 28th, 2012
Recently on Fluther there was a question that referred to the fox-chicken-grain problem as an NP problem. What is NP and how does an NP problem differ from other logic and lateral thinking problems? What are some more examples of NP problems?
Observing members:
0
Composing members:
0
16 Answers
I’m going to go out on a limb and guess that NP here stands for Neurolinguistic Programming… Although that is normally abbreviated to NLP… (have you pm’d the person who wrote NP in their answer?)
Ah, @AshlynM You rock… no amount of NLP is going to help me to understand NP!
@harple glad I was able to help…I had no idea what to search for, just started typing NP and fox and chicken grain.
“NP-complete problem, any of a class of computational problems for which no efficient solution algorithm has been found. Many significant computer-science problems belong to this class—e.g., the traveling salesman problem, satisfiability problems, and graph-covering problems.”
Encyclopedia Britanica
Just remember, it was once thought that we would never have the computational power to crack Enigma, but a few years of warfare got its to develop a warehouse-sized machine to do just that…. and that machine was not nearly as powerful as my phone. A $3000 PC from 2012 is more powerful than a $30,000,000 mainframe from about 20 years ago.
My point is that while certain problems require brute force because there is no simple algorithm, we have more brute force available as time marches on.
Thanks, everybody. I’m still puzzled as to why a relatively simple problem such as the fox-chicken-grain problem was called an NP problem. As @harple suggests, I’ll pm the other poster.
In algorithm analysis (essentially a branch of computer programming), a program is analyzed to see roughly how well it performs with a given input size. An example of this is an algorithm that sorts a list, and in the worst case needs to make ~100 comparisons on a list with 10 elements (or ~10,000 on a list with 100 elements, etc). Such an algorithm is said to have an O(n^2) (“O of n squared”) running time, where n represents the input size (in this example, the number of elements in the list). An NP problem is a problem that requires a higher-order expression (such as an exponential expression like e^n or a factorial expression like n!) to run with any known implementation, but can still be verified in polynomial time. Whether or not NP problems can be solved in polynomial time remains to be seen; and it’s entirely possible that they can be.
It should be noted that NP doesn’t stand for “non-polynomial”, but rather “non-deterministic polynomial”, meaning that a non-deterministic computer (essentially one that can spawn infinite processors and run them all in parallel) could solve any NP problem in polynomial time. This is important since NP problems aren’t necessarily not solvable in polynomial time by a normal computer.
Lastly, as for the fox-chicken-grain problem, it’s probably NP (more specifically, I believe, NP-complete) only in the general case (i.e. allowing for any number of parties with predator-prey relationships). In the 3-case (which humans usually solve), there’s no input, so it’ll always be run in a constant amount of time.
If you like the fox/chicken, etc. problem, try this one…
Same boat, same rule about only holding two people/animals. A lion, its trainer, a mother, a father, their two daughters and their two sons are on one side of a wide river and need to cross to the other side. Only the trainer, the mother and the father can row the boat. The lion must never be left alone with other people unless the trainer is present, or he will eat the people. The mother can never be left with the daughters unless the father is there too…or they will fight. Similarly, the father can never be left with either of the two sons, unless the mother is there…
Okay…get everyone over to the other side… : )
@yankeetooter Can a parent row with a same sex child in the boat?
OK, @yankeetooter two questions:
(1) Does the rule about not leaving someone alone with someone else also apply while in the boat? If so, that means that the only person that can transport the lion over is the trainer, right?
(2) Can the two daughters be left together on one shore without the father being present? (Similarly, can the two sons be left together on one shore without the mother being present.)
1) Yes…only the trainer can transport the lion, just as the mother cannot transport a daughter, etc.
2) Yes, provided the mother is not there (or the father with the sons).
Answer this question 
This question is in the General Section. Responses must be helpful and on-topic.
Composing members:
0
