0

So from what I understand:

NP are problems that can be easy to solve and verify (ie: multiplication)

NP-Hard are problems that are hard to solve but easy to verify (factoring)

What is NP-Complete? The answers I find online say it's almost like NP-hard but I'm having trouble distinguishing the two.

Related: NP-Complete VS NP-Hard

Community
  • 1
  • 1
penu
  • 968
  • 1
  • 9
  • 22
  • 1
    Related, but not an exact duplicate: http://stackoverflow.com/questions/6916162/what-are-np-and-np-complete-problems/6916496#6916496 – templatetypedef Dec 08 '16 at 22:54
  • NP problems are not necessarily "easy" to solve, a solution can just be _verified_ in polynomial time. – e0k Dec 08 '16 at 22:55
  • @e0k then how is it different from np-hard? – penu Dec 08 '16 at 22:56
  • A problem is NP when a proposed solution for it is verifiable in polynomial time (or equivalently, when the problem is solvable in **P**olynomial time by a **N**ondeterministic Turing machine). A problem is NP-Hard when every problem in NP reduces to it. A problem is NP-Complete if it is NP and NP-Hard. "P=NP" is equivalent to "NP=NP-Complete". – BallpointBen Dec 08 '16 at 23:05

2 Answers2

1

NP-complete problems are decision problems and belong to NP (and every problem in NP can be reduced in polynomial time to them, but these details I guess you already saw online).

NP-hard are problems to which any problem in NP can be reduced, but not necessarily belong to NP or are decision problems.

Obviously, every NP-complete problem is also NP-hard (by definition of NP-hard). The opposite is not true, there are problems that are NP-hard but do not belong to NP.

For example, finding count of all solutions to a SAT instance (#SAT) is NP-hard but does not belong to NP-complete class, at least because it is not a decision problem and hence does not belong to NP.

On the other hand, SAT, the problem of deciding if count of satisfying solutions is greater than zero, belongs to NP and every problem in NP can be reduced to it, hence it is NP-complete.

Note, every problem in NP can be reduced to (#SAT) (because SAT can be reduced to #SAT, just find a count and output true if it is non-zero). It is "hard" at least as SAT; this is the intuition behind the name NP-hard.

I would also like to point to an excellent and detailed answer covering more details.

Community
  • 1
  • 1
Coder
  • 51
  • 4
  • What is a SAT problem – penu Dec 08 '16 at 23:24
  • SAT is [boolean satisfability problem](https://en.wikipedia.org/wiki/Boolean_satisfiability_problem), sorry, I assumed you are familiar with because it is cornerstone of the NP-Complete theme (in general it was first formally proven NP-complete problem so everything begins there) – Coder Dec 08 '16 at 23:29
  • I've added links to the answer – Coder Dec 08 '16 at 23:31
  • Sorry I am a noob heh. But what does it mean when a problem can be reduced to an NP problem? – penu Dec 08 '16 at 23:35
  • 1
    For formal definition I've added a [link](https://en.wikipedia.org/wiki/Reduction_(complexity)). Of course, the meaning here was reduced in polynomial time. In _very_ simple words, reduction means that the problem you are reducing to can provide an output that allows to solve the original problem (usually the purpose is to solve easily). For example, if you have an algorithm that returns two minimal values in a list of numbers, the problem of finding minimum number in a list can be reduced to it - run the algorithm for two values and return the one that is less than the other. – Coder Dec 08 '16 at 23:49
  • You may also want to read this [excellent answer] (http://stackoverflow.com/a/6916496/7269637) to a related question. – Coder Dec 08 '16 at 23:52
0

A problem is NP-complete when it is both in NP and NP-hard

A decision problem B is NP-complete if:

1- B is in NP.

2- Every problem in NP is reducible to B in polynomial time. (NP-hard)