5 ms·

What does "NP-complete" mean? Can anyone elaborate?

by staticelf 10y ago

mapleoin 10y ago
https://en.wikipedia.org/wiki/NP-complete https://en.wikipedia.org/wiki/NP-complete
- xrisk 10y ago
  If he wanted a Wikipedia article he would ask for one.
  - Ao7bei3s 10y ago
    It's one of the most fundamental computer science topics. There is absolutely no point in coming up with an ad-hoc explanation or copy/pasting one just to stay on HN instead of linking to a good resource.
    - Mithaldu 10y ago
      He could at least have linked to https://simple.wikipedia.org/wiki/NP-complete https://simple.wikipedia.org/wiki/NP-complete instead.
  - baldfat 10y ago
    I think Wikipedia is the perfect response. It gives the person actual facts (As close as they can get) instead of someone talking off the top of their head or out of their ... If it was a question about an aspect of the topic sure Wiki page is a bad response, but if asking a large whole scale factual question send them the information.
  - dspillett 10y ago
    He did, indirectly. He asked for elaboration on the point and the information on that page is a perfectly good way of elaborating on the subject. If you want something specific, ask for something specific. If you specifically don't want something specifically mention you'd prefer not that.
  - Karunamon 10y ago
    I'm inclined to agree - most people here know what Google is. Asking a group of humans implies a human giving a human readable answer, not a link to an an encyclopedia article that's mostly useless unless you're a CS grad. (Funnily enough, this is acknowledged by the wiki community, looking at the box at the top of the page)
taneq 10y ago
It's confusingly written. In this context, I think they're saying that there's no general polynomial-time algorithm (edit: assuming P != NP, thanks chengsun!) to give you a path through a TrackMania track which will complete the track (as in, visit every waypoint in some order and then reach the finish).
- Rafert 10y ago
  That is why the Simple English Wikipedia is so great: https://simple.wikipedia.org/wiki/NP-complete https://simple.wikipedia.org/wiki/NP-complete
- chengsun 10y ago
  This is only true assuming that P != NP, which is still an unsolved question. Furthermore, NP-completeness only applies to decision problems. In this case the paper explores the problem of deciding whether or not there exists a path which will complete the track. The upshot is, if there exists a polynomial-time algorithm to decide this question, then we can use this algorithm to solve all other NP decision problems in polynomial time.
  - taneq 10y ago
    Good catch, and it'd be hilarious if such a long-standing problem were solved by some person trying to write a bot for a racing game.
s_dev 10y ago
http://alecb.me/blog/p-vs-np http://alecb.me/blog/p-vs-np
jzymbaluk 10y ago
NP-Complete is one of those concepts that takes quite a bit of background knowledge to get a really good handle on. Disclosure: I just finished an undergraduate Algorithm Analysis course this week, so this knowledge is fresh in my mind, I'll try to explain in the way that I learned, but do note that it may not be strictly correct academically. When speaking about the efficiency of a program or algorithm, we frequently use Asymptotic, or "Big-O" notation [1] to describe how the time requirements of a program scale relative to its input. For example, Bubble sort is an example of an O(n^2) Algorithm[2], which means that if it takes 1 second to sort a list of size=10, then it will take roughly 10 seconds to sort a list of size=100. The reason we use Big-O notation is because it gives an idea of how the program will perform on any computer independent of other factors like processor speed. Bubble sort is an example of an algorithm that, while not the most efficient algorithm for sorting, does take polynomial time, which means that its big-O is expressible as some O(n^k) where k is some reasonably small number (My professor says that k<=3 is what many agree as reasonable, but I'm sure that number varies). Many problems however do not have an algorithm that solves the problem in Polynomial time. To solve the Traveling Salesman Problem exactly can take O(n!) time[3], and solving the knapsack problem takes O(2^n) time[4]. Note that there are algorithms that may solve exponential problems such as these approximately, or heuristically in polynomial time, but finding the exact solution takes massive amounts of time for any decently large value of n. It's natural to wonder why some problems are "easy" to solve, and why some are "hard" to solve, researchers have been puzzling over this for some time and have come up with a classification for "easy" and "hard" problems that they call P and NP. For the sake of this classification, we consider an algorithm to have two stages: stage 1 is where the problem is solved and a candidate answer is produced, stage 2 is where the candidate answer produced by stage 1 is verified to be a correct and valid answer to the problem. For a problem to be classified as P (which which stands for Polynomial), both stage 1 and stage 2 of its algorithm must have polynomial time requirements. On the other hand we have NP, which does not stand for Non-Polynomial like you might expect, instead it stands for Non-Deterministically Polynomial. There's a lot of theory behind this concept, but essentially it means that the only possible way for stage 1 of this algorithm to have polynomial time is to resort to non-deterministic algorithms[5], one example of which is an oracle algorithm which will instantly provide you the correct answer magically[6]. NP-complete is a term that means that once stage 1 of an NP-complete algorithm has magically produced the correct answer, stage 2 can still verify that answer in polynomial time. Also note that NP as a set of problems contains all problems in P, since even though a polynomial time stage 1 may exist, the problem still could employ a non-deterministic stage 1 also. The first problem shown to be NP-complete was the Boolean Satisfiability Problem or SAT problem in 1971[7] which asks, given a formula consisting of boolean input statements, AND's, OR's and NOT's, is there any combination of inputs such that the result of the formula is true. Researchers soon discovered that it was possible to show other problems like the 3-CNF SAT problem are NP-complete by showing that problems could be transformed so that they could be solved directly by the SAT algorithm. A good way to think about this is that if you have an algorithm to solve mathematical addition, you could create an algorithm to solve mathematical multiplication by transforming the inputs, for example 2x3 could be transformed into 2+2+2, and this would let you solve multiplication by transforming to addition. This is how researchers today prove that a problem is NP-complete, by reducing their problem to a known NP-complete problem. An interesting side effect of this is that all known NP-complete problems today form a network of transformations, from any problem to any other problem, see [8] for an example of this. This also means that if a true Polynomial solution to ANY NP-complete problem is found, then every other NP-complete problem would also be solved automagically through transformations. From the Abstract of the paper: "We prove that completing an untimed, unbounded track in TrackMania Nations Forever is NP-complete by using a reduction from 3-SAT and showing that a solution can be checked in polynomial time." which means that this researcher takes the TrackMania problem, and reduces it to the 3-SAT to prove that the TrackMania problem is NP-complete Hope this helps. If anyone who knows more than me has any corrections to make, please let me know. [1] https://en.wikipedia.org/wiki/Big_O_notation https://en.wikipedia.org/wiki/Big_O_notation [2] https://en.wikipedia.org/wiki/Bubble_sort https://en.wikipedia.org/wiki/Bubble_sort [3] https://en.wikipedia.org/wiki/Travelling_salesman_problem https://en.wikipedia.org/wiki/Travelling_salesman_problem [4] https://en.wikipedia.org/wiki/Knapsack_problem https://en.wikipedia.org/wiki/Knapsack_problem [5] https://en.wikipedia.org/wiki/Nondeterministic_algorithm https://en.wikipedia.org/wiki/Nondeterministic_algorithm [6] https://en.wikipedia.org/wiki/Oracle_machine https://en.wikipedia.org/wiki/Oracle_machine [7] https://en.wikipedia.org/wiki/Boolean_satisfiability_problem https://en.wikipedia.org/wiki/Boolean_satisfiability_problem [8] https://en.wikipedia.org/wiki/NP-completeness#NP-complete_problems https://en.wikipedia.org/wiki/NP-completeness#NP-complete_pr...

What does "NP-complete" mean? Can anyone elaborate?

mapleoin 10y ago

https://en.wikipedia.org/wiki/NP-complete https://en.wikipedia.org/wiki/NP-complete

xrisk 10y ago
If he wanted a Wikipedia article he would ask for one.
- Ao7bei3s 10y ago
  It's one of the most fundamental computer science topics. There is absolutely no point in coming up with an ad-hoc explanation or copy/pasting one just to stay on HN instead of linking to a good resource.
  - Mithaldu 10y ago
    He could at least have linked to https://simple.wikipedia.org/wiki/NP-complete https://simple.wikipedia.org/wiki/NP-complete instead.
- baldfat 10y ago
  I think Wikipedia is the perfect response. It gives the person actual facts (As close as they can get) instead of someone talking off the top of their head or out of their ... If it was a question about an aspect of the topic sure Wiki page is a bad response, but if asking a large whole scale factual question send them the information.
- dspillett 10y ago
  He did, indirectly. He asked for elaboration on the point and the information on that page is a perfectly good way of elaborating on the subject. If you want something specific, ask for something specific. If you specifically don't want something specifically mention you'd prefer not that.
- Karunamon 10y ago
  I'm inclined to agree - most people here know what Google is. Asking a group of humans implies a human giving a human readable answer, not a link to an an encyclopedia article that's mostly useless unless you're a CS grad. (Funnily enough, this is acknowledged by the wiki community, looking at the box at the top of the page)

taneq 10y ago

It's confusingly written. In this context, I think they're saying that there's no general polynomial-time algorithm (edit: assuming P != NP, thanks chengsun!) to give you a path through a TrackMania track which will complete the track (as in, visit every waypoint in some order and then reach the finish).

Rafert 10y ago
That is why the Simple English Wikipedia is so great: https://simple.wikipedia.org/wiki/NP-complete https://simple.wikipedia.org/wiki/NP-complete
chengsun 10y ago
This is only true assuming that P != NP, which is still an unsolved question. Furthermore, NP-completeness only applies to decision problems. In this case the paper explores the problem of deciding whether or not there exists a path which will complete the track. The upshot is, if there exists a polynomial-time algorithm to decide this question, then we can use this algorithm to solve all other NP decision problems in polynomial time.
- taneq 10y ago
  Good catch, and it'd be hilarious if such a long-standing problem were solved by some person trying to write a bot for a racing game.

s_dev 10y ago

http://alecb.me/blog/p-vs-np http://alecb.me/blog/p-vs-np

jzymbaluk 10y ago

NP-Complete is one of those concepts that takes quite a bit of background knowledge to get a really good handle on. Disclosure: I just finished an undergraduate Algorithm Analysis course this week, so this knowledge is fresh in my mind, I'll try to explain in the way that I learned, but do note that it may not be strictly correct academically. When speaking about the efficiency of a program or algorithm, we frequently use Asymptotic, or "Big-O" notation [1] to describe how the time requirements of a program scale relative to its input. For example, Bubble sort is an example of an O(n^2) Algorithm[2], which means that if it takes 1 second to sort a list of size=10, then it will take roughly 10 seconds to sort a list of size=100. The reason we use Big-O notation is because it gives an idea of how the program will perform on any computer independent of other factors like processor speed. Bubble sort is an example of an algorithm that, while not the most efficient algorithm for sorting, does take polynomial time, which means that its big-O is expressible as some O(n^k) where k is some reasonably small number (My professor says that k<=3 is what many agree as reasonable, but I'm sure that number varies). Many problems however do not have an algorithm that solves the problem in Polynomial time. To solve the Traveling Salesman Problem exactly can take O(n!) time[3], and solving the knapsack problem takes O(2^n) time[4]. Note that there are algorithms that may solve exponential problems such as these approximately, or heuristically in polynomial time, but finding the exact solution takes massive amounts of time for any decently large value of n. It's natural to wonder why some problems are "easy" to solve, and why some are "hard" to solve, researchers have been puzzling over this for some time and have come up with a classification for "easy" and "hard" problems that they call P and NP. For the sake of this classification, we consider an algorithm to have two stages: stage 1 is where the problem is solved and a candidate answer is produced, stage 2 is where the candidate answer produced by stage 1 is verified to be a correct and valid answer to the problem. For a problem to be classified as P (which which stands for Polynomial), both stage 1 and stage 2 of its algorithm must have polynomial time requirements. On the other hand we have NP, which does not stand for Non-Polynomial like you might expect, instead it stands for Non-Deterministically Polynomial. There's a lot of theory behind this concept, but essentially it means that the only possible way for stage 1 of this algorithm to have polynomial time is to resort to non-deterministic algorithms[5], one example of which is an oracle algorithm which will instantly provide you the correct answer magically[6]. NP-complete is a term that means that once stage 1 of an NP-complete algorithm has magically produced the correct answer, stage 2 can still verify that answer in polynomial time. Also note that NP as a set of problems contains all problems in P, since even though a polynomial time stage 1 may exist, the problem still could employ a non-deterministic stage 1 also. The first problem shown to be NP-complete was the Boolean Satisfiability Problem or SAT problem in 1971[7] which asks, given a formula consisting of boolean input statements, AND's, OR's and NOT's, is there any combination of inputs such that the result of the formula is true. Researchers soon discovered that it was possible to show other problems like the 3-CNF SAT problem are NP-complete by showing that problems could be transformed so that they could be solved directly by the SAT algorithm. A good way to think about this is that if you have an algorithm to solve mathematical addition, you could create an algorithm to solve mathematical multiplication by transforming the inputs, for example 2x3 could be transformed into 2+2+2, and this would let you solve multiplication by transforming to addition. This is how researchers today prove that a problem is NP-complete, by reducing their problem to a known NP-complete problem. An interesting side effect of this is that all known NP-complete problems today form a network of transformations, from any problem to any other problem, see [8] for an example of this. This also means that if a true Polynomial solution to ANY NP-complete problem is found, then every other NP-complete problem would also be solved automagically through transformations. From the Abstract of the paper: "We prove that completing an untimed, unbounded track in TrackMania Nations Forever is NP-complete by using a reduction from 3-SAT and showing that a solution can be checked in polynomial time." which means that this researcher takes the TrackMania problem, and reduces it to the 3-SAT to prove that the TrackMania problem is NP-complete Hope this helps. If anyone who knows more than me has any corrections to make, please let me know. [1] https://en.wikipedia.org/wiki/Big_O_notation https://en.wikipedia.org/wiki/Big_O_notation [2] https://en.wikipedia.org/wiki/Bubble_sort https://en.wikipedia.org/wiki/Bubble_sort [3] https://en.wikipedia.org/wiki/Travelling_salesman_problem https://en.wikipedia.org/wiki/Travelling_salesman_problem [4] https://en.wikipedia.org/wiki/Knapsack_problem https://en.wikipedia.org/wiki/Knapsack_problem [5] https://en.wikipedia.org/wiki/Nondeterministic_algorithm https://en.wikipedia.org/wiki/Nondeterministic_algorithm [6] https://en.wikipedia.org/wiki/Oracle_machine https://en.wikipedia.org/wiki/Oracle_machine [7] https://en.wikipedia.org/wiki/Boolean_satisfiability_problem https://en.wikipedia.org/wiki/Boolean_satisfiability_problem [8] https://en.wikipedia.org/wiki/NP-completeness#NP-complete_problems https://en.wikipedia.org/wiki/NP-completeness#NP-complete_pr...