Talk:P versus NP problem

Large edit

Can the large edit be reverted? PiRSquared17 14:57, 15 May 2010 (UTC)

thanks a lot for doing this.

Difficult

I find this simple article harder to understand than the mainstream page. 124.171.59.7 (talk) 09:25, 6 May 2011 (UTC)

I would suggest using the Knapsack problem in the "Example" section. People can relate more easily to packing a bag than building a stack of rocks.

more examples

the more simple examples, the better. you need to give easy P and NP problems examples, only then show what the whole P versus NP is all about.

Too simplified

"NP problems are considered hard for a computer to solve"

This is incorrect... if anything, it's "some" NP problems are considered hard for a computer to solve, which isn't very insightful either.

Hard/Easy

I feel like the hard/easy dichotomy is really computer science jargon. Consider phrasing in terms of fast/slow.

Example "rocks"

All she has to do is melt the rocks then everything becomes uniform and she can easily split the piles into two equal piles without worrying about the individual rocks.74.3.4.112 (talk) 05:28, 11 April 2013 (UTC)

I think I have some solutions for the community to consider in the spirit of the Simple English Wikipedia

Why it matters to Me (Musatov) (parentheticals were to be deleted) but saved.

This question is so important that the Clay Mathematical Institute will give $1,000,000 to anyone who answers it. There are many important NP problems that people don't know how to solve in a way that is faster than testing every possible answer. Here are some examples of problems and their solutions.

• A travelling salesman wants to visit 100 different cities by driving, starting and ending his trip at home. He has a limited supply of gasoline, so he can only drive a total of 10,000 kilometers. He wants to know if he can visit all of the cities without running out of gasoline.

SOLUTION: Take the city the furthest away of the 100 cities and plot it to be the 50th city on the tour. If the 50th city is < 5,000 kilometers he may succeed.

• A school offers 100 different classes, and a teacher needs to choose one hour for each class' final exam. To prevent cheating, all of the students who take a class must take the exam for that class at the same time. If a student takes more than one class, then all of those exams must be at a different time. The teacher wants to know if he can schedule all of the exams in the same day so that every student is able to take the exam for each of their classes.

SOLUTION: Yes, because the time all the students must take the exam for that class is different than all of those exams at a different time.

• A farmer wants to take 100 watermelons of different masses to the market. She needs to pack the watermelons into boxes. Each box can only hold 20 kilograms without breaking. The farmer needs to know if 10 boxes will be enough for her to carry all 100 watermelons to market.

SOLUTION: 100 units 10 boxes 20 kg capacity per box 10 boxes hold 200 kg

As long as each box holds an average of 10 watermelons

10 boxes x 10 watermelons = 100 watermelons

Provided the average weight of a watermelon in a box is 2kg, the watermelons may be packed in any order.

For example if {2, 3, 1, 1, 3} is acceptable in a box of 5 watermelon. Also, {2, 4, 4, 0, 0} is acceptable in a box of 3 watermelons.

But since there are two watermelons with 0 mass, we know we can box the 8 watermelons {2, 3, 1, 1, 3, 2, 4, 4} in one box.

• A large art gallery has many rooms, and each wall is covered with many expensive paintings. The owner of the gallery wants to buy cameras to watch these paintings, in case a thief tries to steal any of them. He wants to know if 100 cameras will be enough for him to make sure that each painting can be seen by at least one camera.

SOLUTION: Yes, provided each painting is seen by an average of 1 camera and no paintings are seen by an average of 0 cameras.

• The principal of a school has a list of which students are friends with each other. She wants to find the largest group of students that are all friends with each other.

SOLUTION: Find the person present as a friend to the largest number of students, then the person who is friend to the second largest number of students, and continue in this fashion until you have included the person who is friend to the least number of students. "74.3.4.112 (talk) 15:07, 11 May 2013 (UTC)"

100 Rocks split in 2 piles = 2^100?

Isn't it true if there is a group of size n (100) that is divided into m (2) subgroups, the total number of possible sub groups, g, is g=n!/[(n/m)! x (n-n/m)!] ? If so, then g = 100!/(50! x (50!) =~ 1e29. Further, since each sub group has two possible divisions that are equal [i.e. g(1) = g(2) and g(2) = g(1)], then g ~ 0.5 e29.

Conservative (conserving) major edit of lede opening

The following changes were made to the lede's opening, prompted by earlier comments in Talk, and by the inability of bright pre-teens to understand this lede (but who arrived at understanding from the lede of the corresponding en.WP article).

In making the edits, most earlier content was kept but reordered, with clarifying content added from the English wikipedia, or otherwise (but see also below). In particular, I addressed Talk comments, regarding the "easy" versus "fast" descriptions, and comments suggesting there was explanatory content at the English wikipedia that might be understandable here. In addition, further important wikilinks were added (e.g., to mathematical proof), with more to come as I familiarize myself with the information available at SEW.

Here are the specific changes made, so issue can be take, and selective reversions made (if necessary):

• the introduced italics that offended an earlier editor was removed;
• an effusion of confusing definite impersonal pronouns ("it" and "it's" appearances) that were difficult to track to their antecedents were addressed;
• the fact that when "easy" was used (when what is implied is "fast") was addressed for sake of clarity, and to address the earlier Talk concerns about accuracy;
• the article was opened with text from the English wikipedia lede that was easily understood by my teen-aged sample audience: "Can every solved problem whose answer can be checked by computer also be quickly solved by a computer?";
• the opening number set example was edited slightly, for clarity, and standard presentation;
• the word "check" was introduced, in the context of "check… the answer" (easily understood by young audiences, even ESL), as a preliminary to introducing the concept of verification (since verify and verification, while arguably simple enough words, are less familiar in general language usage);
• in doing the foregoing, we resolve the issue of the earlier article's going back and forward between the "difficulty metric" and the "speed metric" (making the earlier article lede hard to comprehend), by making them pedagogically synonymous here, thus addressed reader's observations that in their experience, something could be easy but slow;
• the riddle analogy was moved up, and edited for clarity (see also below);
• the sentence on the prize being offered was moved up, as an immediately appreciated fact that was better, contextually, here than where it appeared earlier;
• the "Digging a little deeper…" segue was added to the text that followed, to ease the transition to more detailed content;
• various contractions were expanded, as it is established practice to avoid contractions in formal writing addressed to ESL audiences; and
• paragraphing was changed slightly, to cluster related sentences more fully.

Issues remaining are:

• the "i.e. it's easy to see that it's right and therefore it's also a P problem" [sic.] phrase removed from the riddle analogy text can be returned as "that is, …", if it can be made rigorously correct, the confusing trio of "it's" are removed, and can be otherwise made understandable to a simple reader;
• the sentence closing the riddle analogy should be eliminated, because its vague rendering makes it indecipherable—in the "The fundamental question is, are riddles really as hard as we think they are, or are we just missing something?", try nailing down its meaning by adding "…missing something about… (what?)", because three of us here could not!

Please reply here, and in the spirit of this place, do not simply revert without explanation (in whole or in part). Le Prof Leprof 7272 (talk) 18:44, 31 January 2015 (UTC)

Example section edited

Have a look, and see the edit summary for motivation. In my opinion, the existing math markup (two different text sizes) is unnecessary and cumbersome. As well, the use of physicist-favoured seconds is SI-compliant, but not layperson friendly (hence the introduction of verbal description).

Even use of scientific notation ("1.3 x 10³⁰") is easier, globally, for middle and high school students, in comparing large numbers (more so than long strings of written out numbers), and, e.g., for seeing that the ratio of two numbers in on the order of a trillion. In this regard, the presentation of the numerical strings that report time in seconds are not as pedagogically useful as stating the larger units of days or years (hence, in further part, the edit offered).

Links were also added, and I note that there is no article yet for the mathematical concept of combination (mathematics), making this article all the harder to understand. Le Prof Leprof 7272 (talk) 19:51, 31 January 2015 (UTC)

I did it wrong hold on.

Can't you solve the rocks like this?

Arrange two columns of rocks as they are handed to you. Say you received a 1 pound rock, then a 4 pound rock. Note the 1 pound rock in tower A and the 4 pound rock in tower B. Then remember tower B got the big one of the first two rocks. Then get the next two rocks: 3 pounds and 6 pounds. This time put the bigger of the two rocks in tower A. Then get the next two rocks, say 2 pounds and 7 pounds. It's B's turn to get the big rock so you put the 2 pound rock in tower A and the 7 pound rock in tower B. So for A then you have 1, 6, 2 and for B you have 4, 3, 7. Next you sum the towers: 1 + 6 + 2=9 for tower A. 4 + 3 + 7=14 for tower B. Then figure out the absolute value of the difference between your towers. If the number is odd (as it is in this case as 5) then no solution exists using all the rocks.