Editing 287: NP-Complete

Jump to: navigation, search

Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.

The edit can be undone. Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision Your text
Line 12: Line 12:
 
In {{w|Computational complexity theory|computational complexity theory}}, NP stands for "nondeterministic polynomial time," which means that problems that are NP take polynomial running time (i.e. the time a CPU would take to run the program would be polynomial in the input size) to verify a solution, but it is unknown whether finding any or all solutions can be done in polynomial time. Polynomial time is considered efficient; exponential and higher times are considered unfeasible for computation. NP-complete problems are ones that, if a polynomial time algorithm is found for any of them, then all NP problems have polynomial time solutions. In short, particular guesses in NP-complete problems can be checked easily, but systematically finding solutions is far more difficult.
 
In {{w|Computational complexity theory|computational complexity theory}}, NP stands for "nondeterministic polynomial time," which means that problems that are NP take polynomial running time (i.e. the time a CPU would take to run the program would be polynomial in the input size) to verify a solution, but it is unknown whether finding any or all solutions can be done in polynomial time. Polynomial time is considered efficient; exponential and higher times are considered unfeasible for computation. NP-complete problems are ones that, if a polynomial time algorithm is found for any of them, then all NP problems have polynomial time solutions. In short, particular guesses in NP-complete problems can be checked easily, but systematically finding solutions is far more difficult.
  
βˆ’
The waiter's problem is NP-complete, since a given order's price can be found and checked quickly, but finding an order to match a price is much harder. This causes the order to effectively be an {{w|application layer}} {{w|denial-of-service attack}} / {{w|algorithmic complexity attack}} on the waiter, similar to {{w|Slowloris (computer security)|Slowloris}} or {{w|ReDoS}}. (Formal proofs of the NP-completeness of the knapsack problem can be found at the above link.) The most straightforward way for a human to find a solution is to methodically start by first listing all the (6) ways of choosing one appetizer, and their total costs, then list all the (21) ways of choosing two appetizers (allowing repeats), and then list all the (56) ways of choosing three appetizers, and so forth. As any combination of eight appetizers would be more than $15.05, the process need not extend beyond listing all the (1715) ways of choosing seven appetizers.
+
The waiter's problem is NP-complete, since a given order's price can be found and checked quickly, but finding an order to match a price is much harder. (Formal proofs of the NP-completeness of the knapsack problem can be found at the above link.) The most straightforward way for a human to find a solution is to methodically start by first listing all the (6) ways of choosing one appetizer, and their total costs, then list all the (21) ways of choosing two appetizers (allowing repeats), and then list all the (56) ways of choosing three appetizers, and so forth. As any combination of eight appetizers would be more than $15.05, the process need not extend beyond listing all the (1715) ways of choosing seven appetizers.
  
 
Another famous NP-complete problem is the {{w|Travelling salesman problem|travelling salesman problem}}, mentioned by Cueball at the end, referring to the waiter's claim that he has 6 more tables to get to. (see also [[399: Travelling Salesman Problem]]).
 
Another famous NP-complete problem is the {{w|Travelling salesman problem|travelling salesman problem}}, mentioned by Cueball at the end, referring to the waiter's claim that he has 6 more tables to get to. (see also [[399: Travelling Salesman Problem]]).

Please note that all contributions to explain xkcd may be edited, altered, or removed by other contributors. If you do not want your writing to be edited mercilessly, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource (see explain xkcd:Copyrights for details). Do not submit copyrighted work without permission!

To protect the wiki against automated edit spam, we kindly ask you to solve the following CAPTCHA:

Cancel | Editing help (opens in new window)