What is an NP-complete problem? Why is it such an important topic in computer science?
This question is related to
algorithm
language-agnostic
mathematical-optimization
theory
np-complete
Honestly, Wikipedia might be the best place to look for an answer to this.
If NP = P, then we can solve very hard problems much faster than we thought we could before. If we solve only one NP-Complete problem in P (polynomial) time, then it can be applied to all other problems in the NP-Complete category.
It's a class of problems where we must simulate every possibility to be sure we have the optimal solution.
There are a lot of good heuristics for some NP-Complete problems, but they are only an educated guess at best.
The definitions for NP complete problems above is correct, but I thought I might wax lyrical about their philosophical importance as nobody has addressed that issue yet.
Almost all complex problems you'll come up against will be NP Complete. There's something very fundamental about this class, and which just seems to be computationally different from easily solvable problems. They sort of have their own flavour, and it's not so hard to recognise them. This basically means that any moderately complex algorithm is impossible for you to solve exactly -- scheduling, optimising, packing, covering etc.
But not all is lost if a problem you'll encounter is NP Complete. There is a vast and very technical field where people study approximation algorithms, which will give you guarantees for being close to the solution of an NP complete problem. Some of these are incredibly strong guarantees -- for example, for 3sat, you can get a 7/8 guarantee through a really obvious algorithm. Even better, in reality, there are some very strong heuristics, which excel at giving great answers (but no guarantees!) for these problems.
Note that two very famous problems -- graph isomorphism and factoring -- are not known to be P or NP.
As far as I understand
P is the set of problems which could be solved in polynomial time with a deterministic TM.
NP is the set of problems which requires a non-deterministic TM to be solved in polynomial time. This means that we can check all different combinations of variables in parallel with each instance taking polynomial time. If the problem is solvable then at least one of those parallel instances of TM would halt with "yes". This also means that if you could make a correct guess about the variables/solution then you just need to check it's validity in polynomial time.
NP-Hard is the set where problems are at least as hard as NP. This means NP-Hard problem are equally or more difficult than any problem in NP set.
NP-Complete is the intersection set of NP and NP-Hard. A problems in NP-Complete set can be reduced to any other NP-Complete problem. That means if any of the NP-Complete problem would have an efficient solution then all of the NP-Complete problems could be solved with same solution.
How can you prove P=NP and win a US $1,000,000 prize?
If you could show that every NP problem is reducible to any other NP problem, then NP-Complete set spans over entire NP sets (definition of NP-Complete), i.e NP-Complete=NP. Also since P?NP, this means that at least one of those NP-Complete problem is solvable in polynomial time, which implies that entire NP set can be solved in polynomial time. Clearly it would conclude that P=NP. Well this is just one way to prove P=NP, there might be many other ways.
Please let me know if I made any mistake.
It's a class of problems where we must simulate every possibility to be sure we have the optimal solution.
There are a lot of good heuristics for some NP-Complete problems, but they are only an educated guess at best.
NP Complete problem :-
1 Decision Problem A is called NP complete if it has following two properties:-
Some Ex :-
Honestly, Wikipedia might be the best place to look for an answer to this.
If NP = P, then we can solve very hard problems much faster than we thought we could before. If we solve only one NP-Complete problem in P (polynomial) time, then it can be applied to all other problems in the NP-Complete category.
As far as I understand
P is the set of problems which could be solved in polynomial time with a deterministic TM.
NP is the set of problems which requires a non-deterministic TM to be solved in polynomial time. This means that we can check all different combinations of variables in parallel with each instance taking polynomial time. If the problem is solvable then at least one of those parallel instances of TM would halt with "yes". This also means that if you could make a correct guess about the variables/solution then you just need to check it's validity in polynomial time.
NP-Hard is the set where problems are at least as hard as NP. This means NP-Hard problem are equally or more difficult than any problem in NP set.
NP-Complete is the intersection set of NP and NP-Hard. A problems in NP-Complete set can be reduced to any other NP-Complete problem. That means if any of the NP-Complete problem would have an efficient solution then all of the NP-Complete problems could be solved with same solution.
How can you prove P=NP and win a US $1,000,000 prize?
If you could show that every NP problem is reducible to any other NP problem, then NP-Complete set spans over entire NP sets (definition of NP-Complete), i.e NP-Complete=NP. Also since P?NP, this means that at least one of those NP-Complete problem is solvable in polynomial time, which implies that entire NP set can be solved in polynomial time. Clearly it would conclude that P=NP. Well this is just one way to prove P=NP, there might be many other ways.
Please let me know if I made any mistake.
If you're looking for an example of an NP-complete problem then I suggest you take a look at 3-SAT.
The basic premise is you have an expression in conjunctive normal form, which is a way of saying you have a series of expressions joined by ORs that all must be true:
(a or b) and (b or !c) and (d or !e or f) ...
The 3-SAT problem is to find a solution that will satisfy the expression where each of the OR-expressions has exactly 3 booleans to match:
(a or !b or !c) and (!a or b or !d) and (b or !c or d) ...
A solution to this one might be (a=T, b=T, c=F, d=F). However, no algorithm has been discovered that will solve this problem in the general case in polynomial time. What this means is that the best way to solve this problem is to do essentially a brute force guess-and-check and try different combinations until you find one that works.
What's special about the 3-SAT problem is that ANY NP-complete problem can be reduced to a 3-SAT problem. This means that if you can find a polynomial-time algorithm to solve this problem then you get $1,000,000, not to mention the respect and admiration of computer scientists and mathematicians around the world.
I have heard an explanation, that is:" NP-Completeness is probably one of the more enigmatic ideas in the study of algorithms. "NP" stands for "nondeterministic polynomial time," and is the name for what is called a complexity class to which problems can belong. The important thing about the NP complexity class is that problems within that class can be verified by a polynomial time algorithm. As an example, consider the problem of counting stuff. Suppose there are a bunch of apples on a table. The problem is "How many apples are there?" You are provided with a possible answer, 8. You can verify this answer in polynomial time by using the algorithm of, duh, counting the apples. Counting the apples happens in O(n) (that's Big-oh notation) time, because it takes one step to count each apple. For n apples, you need n steps. This problem is in the NP complexity class.
A problem is classified as NP-complete if it can be shown that it is both NP-Hard and verifiable in polynomial time. Without going too deeply into the discussion of NP-Hard, suffice it to say that there are certain problems to which polynomial time solutions have not been found. That is, it takes something like n! (n factorial) steps to solve them. However, if you're given a solution to an NP-Complete problem, you can verify it in polynomial time.
A classic example of an NP-Complete problem is The Traveling Salesman Problem."
The author: ApoxyButt From: http://www.everything2.com/title/NP-complete
We need to separate algorithms and problems. We write algorithms to solve problems, and they scale in a certain way. Although this is a simplification, let's label an algorithm with a 'P' if the scaling is good enough, and 'NP' if it isn't.
It's helpful to know things about the problems we're trying to solve, rather than the algorithms we use to solve them. So we'll say that all the problems which have a well-scaling algorithm are "in P". And the ones which have a poor-scaling algorithm are "in NP".
That means that lots of simple problems are "in NP" too, because we can write bad algorithms to solve easy problems. It would be good to know which problems in NP are the really tricky ones, but we don't just want to say "it's the ones we haven't found a good algorithm for". After all, I could come up with a problem (call it X) that I think needs a super-amazing algorithm. I tell the world that the best algorithm I could come up with to solve X scales badly, and so I think that X is a really tough problem. But tomorrow, maybe somebody cleverer than me invents an algorithm which solves X and is in P. So this isn't a very good definition of hard problems.
All the same, there are lots of problems in NP that nobody knows a good algorithm for. So if I could prove that X is a certain sort of problem: one where a good algorithm to solve X could also be used, in some roundabout way, to give a good algorithm for every other problem in NP. Well now people might be a bit more convinced that X is a genuinely tricky problem. And in this case we call X NP-Complete.
Basically this world's problems can be categorized as
1) Unsolvable Problem 2) Intractable Problem 3) NP-Problem 4) P-Problem
1)The first one is no solution to the problem. 2)The second is the need exponential time (that is O (2 ^ n) above). 3)The third is called the NP. 4)The fourth is easy problem.
P: refers to a solution of the problem of Polynomial Time.
NP: refers Polynomial Time yet to find a solution. We are not sure there is no Polynomial Time solution, but once you provide a solution, this solution can be verified in Polynomial Time.
NP Complete: refers in Polynomial Time we still yet to find a solution, but it can be verified in Polynomial Time . The problem NPC in NP is the more difficult problem, so if we can prove that we have P solution to NPC problem then NP problems that can be found in P solution.
NP Hard: refers Polynomial Time is yet to find a solution, but it sure is not able to be verified in Polynomial Time . NP Hard problem surpasses NPC difficulty.
The definitions for NP complete problems above is correct, but I thought I might wax lyrical about their philosophical importance as nobody has addressed that issue yet.
Almost all complex problems you'll come up against will be NP Complete. There's something very fundamental about this class, and which just seems to be computationally different from easily solvable problems. They sort of have their own flavour, and it's not so hard to recognise them. This basically means that any moderately complex algorithm is impossible for you to solve exactly -- scheduling, optimising, packing, covering etc.
But not all is lost if a problem you'll encounter is NP Complete. There is a vast and very technical field where people study approximation algorithms, which will give you guarantees for being close to the solution of an NP complete problem. Some of these are incredibly strong guarantees -- for example, for 3sat, you can get a 7/8 guarantee through a really obvious algorithm. Even better, in reality, there are some very strong heuristics, which excel at giving great answers (but no guarantees!) for these problems.
Note that two very famous problems -- graph isomorphism and factoring -- are not known to be P or NP.
NP is the set of all decision problems (questions with a yes-or-no answer) for which the 'yes'-answers can be verified in polynomial time (O(nk) where n is the problem size, and k is a constant) by a deterministic Turing machine. Polynomial time is sometimes used as the definition of fast or quickly.
P is the set of all decision problems which can be solved in polynomial time by a deterministic Turing machine. Since they can be solved in polynomial time, they can also be verified in polynomial time. Therefore P is a subset of NP.
A problem x that is in NP is also in NP-Complete if and only if every other problem in NP can be quickly (ie. in polynomial time) transformed into x.
In other words:
So, what makes NP-Complete so interesting is that if any one of the NP-Complete problems was to be solved quickly, then all NP problems can be solved quickly.
See also the post What's "P=NP?", and why is it such a famous question?
NP-Hard are problems that are at least as hard as the hardest problems in NP. Note that NP-Complete problems are also NP-hard. However not all NP-hard problems are NP (or even a decision problem), despite having NP as a prefix. That is the NP in NP-hard does not mean non-deterministic polynomial time. Yes, this is confusing, but its usage is entrenched and unlikely to change.
We need to separate algorithms and problems. We write algorithms to solve problems, and they scale in a certain way. Although this is a simplification, let's label an algorithm with a 'P' if the scaling is good enough, and 'NP' if it isn't.
It's helpful to know things about the problems we're trying to solve, rather than the algorithms we use to solve them. So we'll say that all the problems which have a well-scaling algorithm are "in P". And the ones which have a poor-scaling algorithm are "in NP".
That means that lots of simple problems are "in NP" too, because we can write bad algorithms to solve easy problems. It would be good to know which problems in NP are the really tricky ones, but we don't just want to say "it's the ones we haven't found a good algorithm for". After all, I could come up with a problem (call it X) that I think needs a super-amazing algorithm. I tell the world that the best algorithm I could come up with to solve X scales badly, and so I think that X is a really tough problem. But tomorrow, maybe somebody cleverer than me invents an algorithm which solves X and is in P. So this isn't a very good definition of hard problems.
All the same, there are lots of problems in NP that nobody knows a good algorithm for. So if I could prove that X is a certain sort of problem: one where a good algorithm to solve X could also be used, in some roundabout way, to give a good algorithm for every other problem in NP. Well now people might be a bit more convinced that X is a genuinely tricky problem. And in this case we call X NP-Complete.
NP-complete problems are a set of problems to each of which any other NP-problem can be reduced in polynomial time, and whose solution may still be verified in polynomial time. That is, any NP problem can be transformed into any of the NP-complete problems. – Informally, an NP-complete problem is an NP problem that is at least as "tough" as any other problem in NP.
Honestly, Wikipedia might be the best place to look for an answer to this.
If NP = P, then we can solve very hard problems much faster than we thought we could before. If we solve only one NP-Complete problem in P (polynomial) time, then it can be applied to all other problems in the NP-Complete category.
NP-Complete means something very specific and you have to be careful or you will get the definition wrong. First, an NP problem is a yes/no problem such that
A problem X is NP-Complete if
If X is NP-complete and a deterministic, polynomial-time algorithm exists that can solve all instances of X correctly (0% false-positives, 0% false-negatives), then any problem in NP can be solved in deterministic-polynomial-time (by reduction to X).
So far, nobody has come up with such a deterministic polynomial-time algorithm, but nobody has proven one doesn't exist (there's a million bucks for anyone who can do either: the is the P = NP problem). That doesn't mean that you can't solve a particular instance of an NP-Complete (or NP-Hard) problem. It just means you can't have something that will work reliably on all instances of a problem the same way you could reliably sort a list of integers. You might very well be able to come up with an algorithm that will work very well on all practical instances of a NP-Hard problem.
Basically this world's problems can be categorized as
1) Unsolvable Problem 2) Intractable Problem 3) NP-Problem 4) P-Problem
1)The first one is no solution to the problem. 2)The second is the need exponential time (that is O (2 ^ n) above). 3)The third is called the NP. 4)The fourth is easy problem.
P: refers to a solution of the problem of Polynomial Time.
NP: refers Polynomial Time yet to find a solution. We are not sure there is no Polynomial Time solution, but once you provide a solution, this solution can be verified in Polynomial Time.
NP Complete: refers in Polynomial Time we still yet to find a solution, but it can be verified in Polynomial Time . The problem NPC in NP is the more difficult problem, so if we can prove that we have P solution to NPC problem then NP problems that can be found in P solution.
NP Hard: refers Polynomial Time is yet to find a solution, but it sure is not able to be verified in Polynomial Time . NP Hard problem surpasses NPC difficulty.
If you're looking for an example of an NP-complete problem then I suggest you take a look at 3-SAT.
The basic premise is you have an expression in conjunctive normal form, which is a way of saying you have a series of expressions joined by ORs that all must be true:
(a or b) and (b or !c) and (d or !e or f) ...
The 3-SAT problem is to find a solution that will satisfy the expression where each of the OR-expressions has exactly 3 booleans to match:
(a or !b or !c) and (!a or b or !d) and (b or !c or d) ...
A solution to this one might be (a=T, b=T, c=F, d=F). However, no algorithm has been discovered that will solve this problem in the general case in polynomial time. What this means is that the best way to solve this problem is to do essentially a brute force guess-and-check and try different combinations until you find one that works.
What's special about the 3-SAT problem is that ANY NP-complete problem can be reduced to a 3-SAT problem. This means that if you can find a polynomial-time algorithm to solve this problem then you get $1,000,000, not to mention the respect and admiration of computer scientists and mathematicians around the world.
NP-Complete is a class of problems.
The class P consists of those problems that are solvable in polynomial time. For example, they could be solved in O(nk) for some constant k, where n is the size of the input. Simply put, you can write a program that will run in reasonable time.
The class NP consists of those problems that are verifiable in polynomial time. That is, if we are given a potential solution, then we could check if the given solution is correct in polynomial time.
Some examples are the Boolean Satisfiability (or SAT) problem, or the Hamiltonian-cycle problem. There are many problems that are known to be in the class NP.
NP-Complete means the problem is at least as hard as any problem in NP.
It is important to computer science because it has been proven that any problem in NP can be transformed into another problem in NP-complete. That means that a solution to any one NP-complete problem is a solution to all NP problems.
Many algorithms in security depends on the fact that no known solutions exist for NP hard problems. It would definitely have a significant impact on computing if a solution were found.
The definitions for NP complete problems above is correct, but I thought I might wax lyrical about their philosophical importance as nobody has addressed that issue yet.
Almost all complex problems you'll come up against will be NP Complete. There's something very fundamental about this class, and which just seems to be computationally different from easily solvable problems. They sort of have their own flavour, and it's not so hard to recognise them. This basically means that any moderately complex algorithm is impossible for you to solve exactly -- scheduling, optimising, packing, covering etc.
But not all is lost if a problem you'll encounter is NP Complete. There is a vast and very technical field where people study approximation algorithms, which will give you guarantees for being close to the solution of an NP complete problem. Some of these are incredibly strong guarantees -- for example, for 3sat, you can get a 7/8 guarantee through a really obvious algorithm. Even better, in reality, there are some very strong heuristics, which excel at giving great answers (but no guarantees!) for these problems.
Note that two very famous problems -- graph isomorphism and factoring -- are not known to be P or NP.
We need to separate algorithms and problems. We write algorithms to solve problems, and they scale in a certain way. Although this is a simplification, let's label an algorithm with a 'P' if the scaling is good enough, and 'NP' if it isn't.
It's helpful to know things about the problems we're trying to solve, rather than the algorithms we use to solve them. So we'll say that all the problems which have a well-scaling algorithm are "in P". And the ones which have a poor-scaling algorithm are "in NP".
That means that lots of simple problems are "in NP" too, because we can write bad algorithms to solve easy problems. It would be good to know which problems in NP are the really tricky ones, but we don't just want to say "it's the ones we haven't found a good algorithm for". After all, I could come up with a problem (call it X) that I think needs a super-amazing algorithm. I tell the world that the best algorithm I could come up with to solve X scales badly, and so I think that X is a really tough problem. But tomorrow, maybe somebody cleverer than me invents an algorithm which solves X and is in P. So this isn't a very good definition of hard problems.
All the same, there are lots of problems in NP that nobody knows a good algorithm for. So if I could prove that X is a certain sort of problem: one where a good algorithm to solve X could also be used, in some roundabout way, to give a good algorithm for every other problem in NP. Well now people might be a bit more convinced that X is a genuinely tricky problem. And in this case we call X NP-Complete.
NP-complete problems are a set of problems to each of which any other NP-problem can be reduced in polynomial time, and whose solution may still be verified in polynomial time. That is, any NP problem can be transformed into any of the NP-complete problems. – Informally, an NP-complete problem is an NP problem that is at least as "tough" as any other problem in NP.
It's a class of problems where we must simulate every possibility to be sure we have the optimal solution.
There are a lot of good heuristics for some NP-Complete problems, but they are only an educated guess at best.
NP-Complete means something very specific and you have to be careful or you will get the definition wrong. First, an NP problem is a yes/no problem such that
A problem X is NP-Complete if
If X is NP-complete and a deterministic, polynomial-time algorithm exists that can solve all instances of X correctly (0% false-positives, 0% false-negatives), then any problem in NP can be solved in deterministic-polynomial-time (by reduction to X).
So far, nobody has come up with such a deterministic polynomial-time algorithm, but nobody has proven one doesn't exist (there's a million bucks for anyone who can do either: the is the P = NP problem). That doesn't mean that you can't solve a particular instance of an NP-Complete (or NP-Hard) problem. It just means you can't have something that will work reliably on all instances of a problem the same way you could reliably sort a list of integers. You might very well be able to come up with an algorithm that will work very well on all practical instances of a NP-Hard problem.
NP-Complete is a class of problems.
The class P consists of those problems that are solvable in polynomial time. For example, they could be solved in O(nk) for some constant k, where n is the size of the input. Simply put, you can write a program that will run in reasonable time.
The class NP consists of those problems that are verifiable in polynomial time. That is, if we are given a potential solution, then we could check if the given solution is correct in polynomial time.
Some examples are the Boolean Satisfiability (or SAT) problem, or the Hamiltonian-cycle problem. There are many problems that are known to be in the class NP.
NP-Complete means the problem is at least as hard as any problem in NP.
It is important to computer science because it has been proven that any problem in NP can be transformed into another problem in NP-complete. That means that a solution to any one NP-complete problem is a solution to all NP problems.
Many algorithms in security depends on the fact that no known solutions exist for NP hard problems. It would definitely have a significant impact on computing if a solution were found.
NP-Complete means something very specific and you have to be careful or you will get the definition wrong. First, an NP problem is a yes/no problem such that
A problem X is NP-Complete if
If X is NP-complete and a deterministic, polynomial-time algorithm exists that can solve all instances of X correctly (0% false-positives, 0% false-negatives), then any problem in NP can be solved in deterministic-polynomial-time (by reduction to X).
So far, nobody has come up with such a deterministic polynomial-time algorithm, but nobody has proven one doesn't exist (there's a million bucks for anyone who can do either: the is the P = NP problem). That doesn't mean that you can't solve a particular instance of an NP-Complete (or NP-Hard) problem. It just means you can't have something that will work reliably on all instances of a problem the same way you could reliably sort a list of integers. You might very well be able to come up with an algorithm that will work very well on all practical instances of a NP-Hard problem.
If you're looking for an example of an NP-complete problem then I suggest you take a look at 3-SAT.
The basic premise is you have an expression in conjunctive normal form, which is a way of saying you have a series of expressions joined by ORs that all must be true:
(a or b) and (b or !c) and (d or !e or f) ...
The 3-SAT problem is to find a solution that will satisfy the expression where each of the OR-expressions has exactly 3 booleans to match:
(a or !b or !c) and (!a or b or !d) and (b or !c or d) ...
A solution to this one might be (a=T, b=T, c=F, d=F). However, no algorithm has been discovered that will solve this problem in the general case in polynomial time. What this means is that the best way to solve this problem is to do essentially a brute force guess-and-check and try different combinations until you find one that works.
What's special about the 3-SAT problem is that ANY NP-complete problem can be reduced to a 3-SAT problem. This means that if you can find a polynomial-time algorithm to solve this problem then you get $1,000,000, not to mention the respect and admiration of computer scientists and mathematicians around the world.
The definitions for NP complete problems above is correct, but I thought I might wax lyrical about their philosophical importance as nobody has addressed that issue yet.
Almost all complex problems you'll come up against will be NP Complete. There's something very fundamental about this class, and which just seems to be computationally different from easily solvable problems. They sort of have their own flavour, and it's not so hard to recognise them. This basically means that any moderately complex algorithm is impossible for you to solve exactly -- scheduling, optimising, packing, covering etc.
But not all is lost if a problem you'll encounter is NP Complete. There is a vast and very technical field where people study approximation algorithms, which will give you guarantees for being close to the solution of an NP complete problem. Some of these are incredibly strong guarantees -- for example, for 3sat, you can get a 7/8 guarantee through a really obvious algorithm. Even better, in reality, there are some very strong heuristics, which excel at giving great answers (but no guarantees!) for these problems.
Note that two very famous problems -- graph isomorphism and factoring -- are not known to be P or NP.
NP is the set of all decision problems (questions with a yes-or-no answer) for which the 'yes'-answers can be verified in polynomial time (O(nk) where n is the problem size, and k is a constant) by a deterministic Turing machine. Polynomial time is sometimes used as the definition of fast or quickly.
P is the set of all decision problems which can be solved in polynomial time by a deterministic Turing machine. Since they can be solved in polynomial time, they can also be verified in polynomial time. Therefore P is a subset of NP.
A problem x that is in NP is also in NP-Complete if and only if every other problem in NP can be quickly (ie. in polynomial time) transformed into x.
In other words:
So, what makes NP-Complete so interesting is that if any one of the NP-Complete problems was to be solved quickly, then all NP problems can be solved quickly.
See also the post What's "P=NP?", and why is it such a famous question?
NP-Hard are problems that are at least as hard as the hardest problems in NP. Note that NP-Complete problems are also NP-hard. However not all NP-hard problems are NP (or even a decision problem), despite having NP as a prefix. That is the NP in NP-hard does not mean non-deterministic polynomial time. Yes, this is confusing, but its usage is entrenched and unlikely to change.
We need to separate algorithms and problems. We write algorithms to solve problems, and they scale in a certain way. Although this is a simplification, let's label an algorithm with a 'P' if the scaling is good enough, and 'NP' if it isn't.
It's helpful to know things about the problems we're trying to solve, rather than the algorithms we use to solve them. So we'll say that all the problems which have a well-scaling algorithm are "in P". And the ones which have a poor-scaling algorithm are "in NP".
That means that lots of simple problems are "in NP" too, because we can write bad algorithms to solve easy problems. It would be good to know which problems in NP are the really tricky ones, but we don't just want to say "it's the ones we haven't found a good algorithm for". After all, I could come up with a problem (call it X) that I think needs a super-amazing algorithm. I tell the world that the best algorithm I could come up with to solve X scales badly, and so I think that X is a really tough problem. But tomorrow, maybe somebody cleverer than me invents an algorithm which solves X and is in P. So this isn't a very good definition of hard problems.
All the same, there are lots of problems in NP that nobody knows a good algorithm for. So if I could prove that X is a certain sort of problem: one where a good algorithm to solve X could also be used, in some roundabout way, to give a good algorithm for every other problem in NP. Well now people might be a bit more convinced that X is a genuinely tricky problem. And in this case we call X NP-Complete.
NP is the set of all decision problems (questions with a yes-or-no answer) for which the 'yes'-answers can be verified in polynomial time (O(nk) where n is the problem size, and k is a constant) by a deterministic Turing machine. Polynomial time is sometimes used as the definition of fast or quickly.
P is the set of all decision problems which can be solved in polynomial time by a deterministic Turing machine. Since they can be solved in polynomial time, they can also be verified in polynomial time. Therefore P is a subset of NP.
A problem x that is in NP is also in NP-Complete if and only if every other problem in NP can be quickly (ie. in polynomial time) transformed into x.
In other words:
So, what makes NP-Complete so interesting is that if any one of the NP-Complete problems was to be solved quickly, then all NP problems can be solved quickly.
See also the post What's "P=NP?", and why is it such a famous question?
NP-Hard are problems that are at least as hard as the hardest problems in NP. Note that NP-Complete problems are also NP-hard. However not all NP-hard problems are NP (or even a decision problem), despite having NP as a prefix. That is the NP in NP-hard does not mean non-deterministic polynomial time. Yes, this is confusing, but its usage is entrenched and unlikely to change.
NP Complete problem :-
1 Decision Problem A is called NP complete if it has following two properties:-
Some Ex :-
Honestly, Wikipedia might be the best place to look for an answer to this.
If NP = P, then we can solve very hard problems much faster than we thought we could before. If we solve only one NP-Complete problem in P (polynomial) time, then it can be applied to all other problems in the NP-Complete category.
NP-Complete is a class of problems.
The class P consists of those problems that are solvable in polynomial time. For example, they could be solved in O(nk) for some constant k, where n is the size of the input. Simply put, you can write a program that will run in reasonable time.
The class NP consists of those problems that are verifiable in polynomial time. That is, if we are given a potential solution, then we could check if the given solution is correct in polynomial time.
Some examples are the Boolean Satisfiability (or SAT) problem, or the Hamiltonian-cycle problem. There are many problems that are known to be in the class NP.
NP-Complete means the problem is at least as hard as any problem in NP.
It is important to computer science because it has been proven that any problem in NP can be transformed into another problem in NP-complete. That means that a solution to any one NP-complete problem is a solution to all NP problems.
Many algorithms in security depends on the fact that no known solutions exist for NP hard problems. It would definitely have a significant impact on computing if a solution were found.
NP is the set of all decision problems (questions with a yes-or-no answer) for which the 'yes'-answers can be verified in polynomial time (O(nk) where n is the problem size, and k is a constant) by a deterministic Turing machine. Polynomial time is sometimes used as the definition of fast or quickly.
P is the set of all decision problems which can be solved in polynomial time by a deterministic Turing machine. Since they can be solved in polynomial time, they can also be verified in polynomial time. Therefore P is a subset of NP.
A problem x that is in NP is also in NP-Complete if and only if every other problem in NP can be quickly (ie. in polynomial time) transformed into x.
In other words:
So, what makes NP-Complete so interesting is that if any one of the NP-Complete problems was to be solved quickly, then all NP problems can be solved quickly.
See also the post What's "P=NP?", and why is it such a famous question?
NP-Hard are problems that are at least as hard as the hardest problems in NP. Note that NP-Complete problems are also NP-hard. However not all NP-hard problems are NP (or even a decision problem), despite having NP as a prefix. That is the NP in NP-hard does not mean non-deterministic polynomial time. Yes, this is confusing, but its usage is entrenched and unlikely to change.
NP-Complete means something very specific and you have to be careful or you will get the definition wrong. First, an NP problem is a yes/no problem such that
A problem X is NP-Complete if
If X is NP-complete and a deterministic, polynomial-time algorithm exists that can solve all instances of X correctly (0% false-positives, 0% false-negatives), then any problem in NP can be solved in deterministic-polynomial-time (by reduction to X).
So far, nobody has come up with such a deterministic polynomial-time algorithm, but nobody has proven one doesn't exist (there's a million bucks for anyone who can do either: the is the P = NP problem). That doesn't mean that you can't solve a particular instance of an NP-Complete (or NP-Hard) problem. It just means you can't have something that will work reliably on all instances of a problem the same way you could reliably sort a list of integers. You might very well be able to come up with an algorithm that will work very well on all practical instances of a NP-Hard problem.
I have heard an explanation, that is:" NP-Completeness is probably one of the more enigmatic ideas in the study of algorithms. "NP" stands for "nondeterministic polynomial time," and is the name for what is called a complexity class to which problems can belong. The important thing about the NP complexity class is that problems within that class can be verified by a polynomial time algorithm. As an example, consider the problem of counting stuff. Suppose there are a bunch of apples on a table. The problem is "How many apples are there?" You are provided with a possible answer, 8. You can verify this answer in polynomial time by using the algorithm of, duh, counting the apples. Counting the apples happens in O(n) (that's Big-oh notation) time, because it takes one step to count each apple. For n apples, you need n steps. This problem is in the NP complexity class.
A problem is classified as NP-complete if it can be shown that it is both NP-Hard and verifiable in polynomial time. Without going too deeply into the discussion of NP-Hard, suffice it to say that there are certain problems to which polynomial time solutions have not been found. That is, it takes something like n! (n factorial) steps to solve them. However, if you're given a solution to an NP-Complete problem, you can verify it in polynomial time.
A classic example of an NP-Complete problem is The Traveling Salesman Problem."
The author: ApoxyButt From: http://www.everything2.com/title/NP-complete
If you're looking for an example of an NP-complete problem then I suggest you take a look at 3-SAT.
The basic premise is you have an expression in conjunctive normal form, which is a way of saying you have a series of expressions joined by ORs that all must be true:
(a or b) and (b or !c) and (d or !e or f) ...
The 3-SAT problem is to find a solution that will satisfy the expression where each of the OR-expressions has exactly 3 booleans to match:
(a or !b or !c) and (!a or b or !d) and (b or !c or d) ...
A solution to this one might be (a=T, b=T, c=F, d=F). However, no algorithm has been discovered that will solve this problem in the general case in polynomial time. What this means is that the best way to solve this problem is to do essentially a brute force guess-and-check and try different combinations until you find one that works.
What's special about the 3-SAT problem is that ANY NP-complete problem can be reduced to a 3-SAT problem. This means that if you can find a polynomial-time algorithm to solve this problem then you get $1,000,000, not to mention the respect and admiration of computer scientists and mathematicians around the world.
Source: Stackoverflow.com