complexity theory

 

Why is NP-hard unequal to NP-complete?

My informal understanding of definitions being used:

NP - all problems that can be verified in polynomial time

NP-complete - all problems that are NP and NP-hard

NP-hard - at least as hard as the hardest problem in NP

Decision Problem - A problem that asks a question with regards to an input and outputs a bool value

Confusion:

The problem with unknown solution of P vs NP arises from the fact that we cannot prove or disprove all problems in NP can be solved in polynomial time. It feels like a similar question arises from NP-complete vs NP-hard. How do we know all problems in NP-hard cannot be verified in polynomial time and thus result in NP-hard=NP-complete?

Here is my line of reasoning

From online research the distinction seems that this has something to do with decision problems (a concept I'm entirely new to but seem simple enough). I think this means that problems in NP have complementary decision problems that ask if an input is the solution to the problem. Let's say the problem is to find an optimal solution. I believe the complementary decision problem to be "is the given input the optimal solution?"and I believe that if this decision problem is verifiable in polynomial time then the problem is NP-complete (or in NP). So this means that NP-hard problems that aren't NP-complete problems are those that either have no decision problem (which I believe is never true since any brute force solution can answer this) or a problem is NP-hard and not NP-complete if it has a decision problem that's not verifiable in polynomial time. If it is the latter then it feels like we have the same problem from P vs NP. That is, how do we confirm all decision problems in NP-hard do not have polynomial time solutions?

Sorry if the above phrasing is weird. I will try and clarify any confusion in my question.

notes

I am interested in both an intuitive explanation and a formal explanation (a proof if it's a complicated answer). The formal explanation can certainly be a link to an academic paper. I don't want anyone to invest a significant amount of time into an overly complicated proof that may be beyond the scope of my understanding (I've found complexity theory to become very quickly... complex).

If it helps for the sake of explanation I have done work on the traveling salesman problem and I am currently working on a paper for the nurse scheduling problem (I believe these are NP-hard problems).

NP-Hard includes all problems whose solutions can be used to derive solutions to problems in NP with polynomial overhead.

This includes lots of problems that aren't in NP. For instance, the halting problem - an undecidable problem - is NP-Hard, because any problem in NP can be reduced to it in polynomial time:

  • Reduce any problem in NP to an instance of the NP-Complete problem 3-SAT
  • Construct in polynomial time a TM which checks all assignments and halts iff a satisfying assignment is found.
  • Use a solution to the halting problem to tell whether the TM halts.
  • If it halts, accept; otherwise, reject.
    • 链接地址: http://www.djcxy.com/p/6804.html

    上一篇: 是大O（logn）日志基础？

    下一篇: 复杂性理论