Talk:NP-hard

From Wikipedia, the free encyclopedia

 This article is within the scope of WikiProject Computer science, which aims to create a comprehensive computer science reference for Wikipedia. Visit the project page for more information and to join in on related discussions.
Start rated as start-Class on the assessment scale
Top rated as top-importance on the assessment scale

The claim that NP-complete = NP intersected with NP-hard seems to be unproven and unlikely, given the discussion at the end of NP-complete. Or should we use a different definition of NP-hard? AxelBoldt 21:58 Dec 18, 2002 (UTC)

As far as I know this is the usual definition of NP-complete. It is for example the definition used in Computational Complexity by Christos H. Papadimitriou and I regard that as a more or less authorative work. (I give instructions for a course on computational complexity from this book.) However, I'm not sure why you think this is incompatible with the definition of NP-hard as it is now given in the article. As far as the alternative approach described at the end of NP-complete is concerned, I am not familiar with that approach and I'm not sure I completely understand the definition that is given there. I'll go and see if I can find something about it. -- Jan Hidders 23:00 Dec 18, 2002 (UTC)
PS. Interesting links:

The difference is the following: NP-Complete is usually defined as those NP problems C such that any NP problem P can be polynomial time reduced to C, in the sense that there's a polynomial time computable function f which turns instances of P into instances of C. This is also the definition employed by our NP-Complete article. Now, by employing our definition of NP-hard, the intersection of NP-hard and NP is a (possibly) slightly different set: it is the set of all NP problems C such that any NP problem P can be solved in polynomial time given an oracle for C. Such an oracle can be called multiple times in the course of solving an instance of P, while the polynomial-time-reducible approach from above pretty much requires that the oracle be called only once, as the last statement of your program.

The last link above (lec4hand.ps) makes the same point, and does therefore not define NP-complete as the intersection of NP-hard and NP. AxelBoldt 19:46 Dec 19, 2002 (UTC)

My mistake. I forgot to look at the definition in the article we are supposed to be discussing here. The definition in NP-hard is not what I would consider the most common one, that is the one with polytime many-one reductions, but we should probably also mention the oracle-based definition. I'll get on it. -- Jan Hidders 20:31 Dec 19, 2002 (UTC)
If we want to allow non-decision problems for NP-hard, which seems to be standard, then I don't see a way to define it without oracles though. AxelBoldt 22:20 Dec 19, 2002 (UTC)
AFAIK that is not usual. The only place I know where this happens is in Garey and Johnson's Computers and Intractability and they admit explicitly on page 120 (in section 5.2 on "A Terminological History") that their definition is a generalization of the usual one for decision problems. They also state there that both definitions (the one with Cook reductions and the one with Karp reductions) appear in the literature and neither one of them seems to predominate. It is my own experience that the one with Karp reductions is more common so I have made that now "the" definition and moved the other definition to the end. Note that there are a few ways in which Cook reductions are "problematic". For example, co-NP-hard and NP-hard become the same (but Donald Knuth considered that actually an advantage) and we don't know if NP is closed under Cook reductions. -- Jan Hidders 10:38 Dec 20, 2002 (UTC)

We still have a problem with the definitions. NP-equivalent assumes that NP-hard is a class of general problems, not decision problems. What is the common way to define NP-equivalent? We probably should also check all the pages that link to NP-hard. AxelBoldt 00:45 Jan 24, 2003 (UTC)

The term NP-easy and NP-equivalent were introduced by Garey and Johnson (along with their definition of NP-hard) as classes of search problems. They define NP-equivalent as the intersection of NP-hard and NP-easy. To make things a bit more confusing Papadimitriou calls search problems function problems (even though they do not concern not areally functions) and defines classes such as FP and FNP (and FP-complete and FNP-complete). By the way such problems seem to be what is meant with the definiton of problem at the beginning of decision problem although the definition there is not strict enough for my taste. Anyway, I'm a bit busy at the moment, so I'll get back on this. -- Jan Hidders 13:18 Jan 24, 2003 (UTC)


Hey guys ... I know this is probably sacriligous but could someone please write atleast a paragraph to just quickly summarise what an NP-hard problem is to non-computing people? - Gaurav

Firstly nothing sacrilegious about Gaurav's request. Most encyclopedias are written with a point of view of introducing people to subjects they know very little about and as a quick reference.

However, I am unhappy with the complexity theoretic pages. I am a purist and strictly speaking all this talk about decision problems and optimization problems is not really relevant from a classical complexity theoretic (Not including things like hardness of approximation) point of view. The reason for this is that in the original Turing machine oriented complexity theory NP is a class of languages not a class of problems. The definition of NP as the class of languages accepted by non-deterministically polynomial-time Turing machines (or equivalent) I think is the most elegant. I would like ideally to have all the complexity theory pages written with this focus. However I would like to know what others think about this. - Viz

That's good. We need to keep the problems, because they are interesting, but yeah we need to clarify that NP/P are algorithms that accept languages over strings of alphabets in mk time or whatever. Poor Yorick

Contents

[edit] ============================================================

I am myself a pure mathematician. My problem is why do you use always mathematics to solve a problem. Are there no sciences who have also methods.

I look at NP in another way, an inductive way

Some link

http://nnw.berlios.de/docs.php/intro-math

I could give more links.

Ed van der Meulen

Hi, im a student at uni and part of one of my projects is to find out a definition of NP-hard. I know someone asked for a simpler definition earlier, but i was wondering if i could get a completely simple definition as i have to put the definition into my report in the simplest way i can, and i dont fully understand the above definition. Please try!!

It depends on what definition you would like. Deductive mathematics is going out from axioms and then you have to describe it in an exact way without margins.

Inductive mathematics shows margins. A number gets a margin. This is also exact. You have hard and weak margins. NP is for me in the inductive mathematics unpredictable, there's a physical contingent behavior. With surprises and bad accidents. Other parts in inductive mathematics is the notion of mathematical induction. Also discrete mathematics.

This leads also to more clear definitions of chaos and indeterminism.

The current definition of deductive indeterministic is instead of a function at each decision point there is a relation that tells this input has to go to that SET of outputs. But it stays deductive and in fact repeatable. Not like nature.

I see the difference between deductive determinism / indeterminism as a quantitative difference. You can break it down from complex to simple. But unexpected things you can't break down. Think of the Heisenberg uncertainty. That is a qualitative difference. And so more important.

This is a link about it.

http://nnw-np.sourceforge.net/docs.php/nnw-np-3/noflash

Deductive mathematics is bound to axioms. A very good way. But the reverse way is possible as well. Going from different signs to more exact. Those signs we can get in all ways. Every sign can count. Scientists are using that when they make a profitable hypothesis. Mathematicians use it as well. Trying a hunch. Looking for confirmations.

An inductive game to understand what inductive means here. It's inserting notions from physics and common live. We can make simulationtools with it like for the weather forecast. Earthquakes. Power outages. Teaching and testing like flight simulator also with critical situations.

http://nnw.berlios.de/docs.php/intro-eleu

Simulation tools don't have to work with predicted results. The have to be close to nature. And in natere everything is shifting. Like in this paper.

http://nnw.berlios.de/docs.php/introftk32.

This is also the realm of discrete mathematics.

Inductive tools for simulating have to work together with analyzing tools made with deductive mathematics. Don't throw anything away.

Inductive is already a common notion. I like to articulate it. Have a good day.

I found the definition of NP-hard given somewhat unclear and inconsistent. There were several problems.

The first paragraph defines it as a set of problems, The next (implicitly) as a set of languages, which itself is not defined in-situ or linked to.

The definition is not of the usual form, vis: "a set H where h is a member of H iff Prop(h) holds.", but describes a property of the set H, which does not imply a unique set and so doesn't define membership.

Given that I know (from other Wiki pages) that a reduction is a particular type of transformation between problems, and polynomial-time many-one reductions (PTMOR) are a subset of these, then from the first incomplete definition (which talks about reducing a problem to a class of problems) in the first paragraph, I could reasonably infer the definition to be:

 h in NP-hard iff there exists l in NP and there exists r in PTMOR such that h = r(l)

which would imply that NP-hard includes "the decision problems that are at least as hard as some problem in NP", or

 h in NP-hard iff for all l in NP there exists r in PTMOR such that h = r(l)

which would imply NP-hard includes "the decision problems that are at least as hard as any problem in NP" which is written but seems less plausible (why should all NP problems be reducible to the same one).

It would be nice to see a "definition" which (a) is a definition, (b) is complete in describing the relationships between different entities, (c) links all non-trivial mathematical entities to the defining pages and (d) is consistent with the definitions on other pages.

[edit] Not a decision problem

I don't think NP-Hard is a decision problem. It can be but doesn't have to be. —The preceding unsigned comment was added by 70.178.216.202 (talk • contribs) March 8 (UTC)

That's right. I quote (from ["Fundamentals of algorithmics", Brassard and Bradley, 1996]), In particular, NP-hard problems do not have to be decision problems.. The definition of NP-hard is just "at least as hard as an NP-complete problem". The only difference to NP-comlete is that those problems also have to be in NP (and this is what forces NP-complete problems to be decision problem). —The preceding unsigned comment was added by 129.16.80.125 (talk • contribs) August 10 (UTC)
If NP-Hard problems aren't necessarily decision problems, then they certainly aren't defined in terms of many-one reduction, which reduces decision problems to decision problems. I'm in favor of keeping the definition in terms of many-one reduction, and so am changing the article to make NP-Hard problems only decision problems. I think it's more important to be consistent than to agree with authorities, since there's not general agreement among authorities. LWizard @ 02:56, 22 November 2006 (UTC)
Could anyone give an example that there's not general agreement among authorities. That is I wonder an example of a book or other source, where NPH is defined as a subclass of decision problems. kuszi 14:43, 12 February 2007 (UTC)
How about NIST? [1] LWizard @ 00:45, 13 February 2007 (UTC)
This source contradicts itself in the second sentence. kuszi (talk) 17:20, 30 May 2008 (UTC).
Sir! You make a mistake by saying and doing as written: "I think it's more important to be consistent than to agree with authorities, since there's not general agreement among authorities." Your role is not to define NP-hardness theory anew as you think it should be defined to be internally consistent, or to make it consistent with your view. The definition should reflect the state of knowledge, and what the scientific world thinks about NP-hardness, and the way it is being used. In the field o combinatorial optimization NP-hard probles are considered to be optimization problems, thus certainly not decision problems! (see eg. http://en.wikipedia.org/wiki/Travelling_salesman_problem#NP-hardness). Indeed, NP-hard problems are not defined in terms of decision-to-decision problem transformation. NP-hard problems are defined in terms of polynomial Turing transformation. Dmaciej 22:10, 12 February 2007 (UTC)
My point is that different groups of people use "NP-Hard" in (slightly) different ways. We don't want to take part of the definition from one group and the rest from the other such that what we say makes no sense. So I wasn't "redefining" NP-Hardness, I was changing the article so that it agreed entirely with one definition of NP-Hardness (the complexity theorists') rather than being a nonsensical mix of two definitions. And it is frequently defined in terms of decision problems: see for instance the link to NIST above. Your reference to another Wikipedia article that doesn't cite its sources is much less impressive. Note that we do treat the optimization definition in the article, in the last section LWizard @ 00:45, 13 February 2007 (UTC)


In fact you did redefine NP-hard by making them only decision problems. To verify that NP-hard referes to search or optimization/function problems as well, you should have a look into any book on combinatorial optimization, for example (by chance it is the only book I have in my office now): P.Brucker, Scheduling Algorithms, Springer,1998, p.45, there are numerous other sources which I do not have here at hand, look in Google for articles with "combinatrial optimization + NP-hard". For example: http://www.mathematik.uni-osnabrueck.de/research/OR/class/ You will find numerous references to articles on NP-hard scheduling (optimization!) problems there. Furthermore, there is a contradiction in the NIST definition because 1) it is said that NP-hard problems are decision problems, 2) in the second sentence it is said that optimization version of some NP-complete decision problem is NP-hard. (BTW statement "2)" of NIST definition is true as a by-product of some other definitions, but is not a definition of NP-hard itself). Thus, the definition indeed relies on decision problems, but does not restrict NP-hard to NP, and hence to decision problems. Dmaciej 08:52, 13 February 2007 (UTC).
And one more funny observation. Note, that the definitions of NP-complete, and NP-hard on this wikipedia are cyclic :-)
I understand and admit that many people use "NP-Hard" to refer to optimization problems. However, another large group of people uses "NP-Hard" to refer only to decision problems and not to any other kind of problem. For instance, picking up a book off my desk, M. Sipser's "Introduction to the Theory of Computation" (Thomson, 2006, p.298) defines NP-Hard in terms of many-one (mapping) reduction, which is only defined on decision problems. It is not that the decision-problem definition is just less thorough than the other definition; they are incompatible definitions. We need to recognize this. That said, if you would like to "reverse" the article, i.e. make the lead definition in terms of Turing reduction and applicable to any sort of problem and relegate the decision problem definition to the "Alternative definitions" section, that's fine with me. I just don't want them blended together. LWizard @ 11:31, 13 February 2007 (UTC)
So it contrdicts the accumulated knowledge of 30 years of research. More evidence that NP-hard problems are not only decision problems: 1) B.Korte, J.Vygen, 'Combinatorial Optimization', Springer, 2002: page 352, Definition 15.34: "An optimization problem or a decision problem ... is NP-hard ...."; 2) Ch.Papadimitriou, K.Steiglitz, 'Combinatorial Optimization: Algorithms and Complexity', Prentice-Hall, 1982, page 398 "Besides its use to describe recognition problems not known to be in NP, the term NP-hard is sometimes used in the literature to describe optimization problems"; 3) V.Vazirani, Approximation Algorithms, Springer 2003, see Introduction because I have only a translation of this book but I read here that most of optimization problems are NP-hard. 4) Garey,Johnson define NP-hard in the context of string relations, and search problems (page 113). I agree that polynomial time transformation is something different than polynomial Turing reduction. I do recognize this. Dmaciej 20:25, 13 February 2007 (UTC)

Sipser is not the only one who uses that definition. See e.g. this paper, which has a footnote explaining that many people imprecisely use "NP-Hard" to refer to function problems, and that they will do so as well. LWizard @ 09:56, 14 February 2007 (UTC)

 :-) Using your own words: "Your reference to ...", some article somewhere (these are my words) "... that doesn't cite its sources is much less impressive" :-) This was supposed to be funny :-) I do not see a contradiction even between this footnote and my position about NP-hard problems. What does word precisely or imprecisely mean, and who understands something more precisely is beyond the scientific verification. BTW you should remove TSP from examples section becasue TSP is an optimization problem.
So let's sum up. I gave evidence of books, and network resources (e.g. http://www.mathematik.uni-osnabrueck.de/research/OR/class/ with a list of over 100 publications) where notion NP-hard is used by researchers from all over the world to denote various types of problems which are not in NP, or not known to be in NP, and optimization problems in particular. Dmaciej 11:13, 14 February 2007 (UTC)
Alright, fine, I've turned the article around so that the broader definition is the lead definition. Is this better? LWizard @ 00:33, 15 February 2007 (UTC)
I hope it is better. Thank you. Let's wait for comments from the audience. Dmaciej 08:13, 15 February 2007 (UTC)

Could it be that optimization problems are called NP-hard by a slight abuse of language simply because it is always possible to transform an optimization problem into a decisional one? I.e. an optimization problem is "NP-hard" if its underlying decisonal problem is?. In other words, I am asking if a rigourous definition of NP-hardness always makes a claim on a decisional problem.

On another ground, would it make the article simpler if NP-hardness was defined as "L is NP-hard if L < SAT"?

Powo (talk) 14:06, 1 February 2008 (UTC)

[edit] Impossible to understand

I'm not a stupid person. Granted, I haven't taken a math course since my high school years, but I am not utterly incapable of understanding math. I even have had flashes of understanding the basic implications of P=NP. This said, this article is absolute gibberish to my eyes - polynomial time? Truth value assignments? I can stop and think and squirt a little bit of sense out from this article, but pity be to the poor chump just looking for a quick, easily digestible explanation. I'm not saying that the technical explanation isn't valid (I don't think I'm qualified to even read it), but this article really needs a coherant opening, with the algebraic greek gibberish moved to "section 1 - technical description" or some such. I have thusly tagged this page as {{cleanup-confusing|February 2007}} and {{technical}}. --Action Jackson IV 02:15, 4 February 2007 (UTC) -- Maybe I am a stupid person, as I missed the very first line at the top of the page. --Action Jackson IV 02:17, 4 February 2007 (UTC)

[edit] Halting is NP-Hard?

I couldn't help but notice this edit and would like to know: why is the halting problem NP-Hard? It makes little sense. And NP-Hard problem is a problem that can be decided by a Non-deterministic turing machine (to put it simply), but this problem we know to be undecidable: that is, no Turing machine can decide the halting problem. This, to me, seem like a contradiction. --Stux 11:13, 27 March 2007 (UTC)

An NP-Hard problem is one at least as hard as problems in NP. It is emphatically not necessarily a problem that can be solved by a non-deterministic Turing machine in polynomial time. As noted, a machine with an oracle for the halting problem can solve SAT (which is NP-Complete), and therefore Halting is NP-Hard.
I admit the halting problem might not be the best example. If we chose a problem harder than NP but still decidable (e.g. Regular Expression Inequivalence) that might be clearer. However, there is also value in pointing out that undecidable problems are NP-Hard. LWizard @ 23:34, 27 March 2007 (UTC)

[edit] NP-easy is not necessarily in NP??

Something doesn't seem right here: "NP-easy - stands for 'at most' as hard as NP (but not necessarily in NP); NP-equivalent - means equally difficult as NP, (but not necessarily in NP);"

Surely NP-easy and NP-equivalent are necessarily in NP (?) Is it because NP is only for decision problems, not search/function problems? What if you make a language of every problem instance concatenated with its solutions, that would be in NP; can you then say that such a search problem is in NP?Frank Guerin 13:39, 16 May 2007 (UTC)

Well, my impressions about your comment:
  • Aren't you mislead by the names of the classes?
  • "Is it because NP is only for decision problems, not search/function problems?" - Yest it is a good point.
  • "What if you make a language of every problem instance concatenated with its solutions, that would be in NP; can you then say that such a search problem is in NP?" I am not sure what you want to do with the instances encoded in this way. If you want to check if the solution is good, then it would be a decision problem. However, not necessarily in NP, because it is not known if the solution can be verified in polynomial time.

Dmaciej 14:19, 27 May 2007 (UTC)

[edit] Links

What has emergence to do with this article? Probably I should edit this straight away, but I'm curious. --134.58.253.57 17:38, 5 June 2007 (UTC)

[edit] Tetris

For a more familiar NP-Hard problem, how about Tetris? See here: http://www.arxiv.org/abs/cs.CC/0210020 It will be easier for people to see what NP-hard means if you can read about something like a popular game and see how it relates.

"Scientists agree: Tetris is hard." 24.218.46.235 03:28, 24 September 2007 (UTC)

Maybe I am overly optimistic, but I would assume that the number of readers who are familiar with integers is larger than the number of readers who are familiar with Tetris. Further, "Tetris is hard" is clearly misleading, since "Tetris" is not a well-defined computational problem. In fact, the decision problems which are NP-hart are very much different from the problems an actual Tetris player needs to solve. --Mellum 19:39, 24 September 2007 (UTC)

[edit] Comment

I've just removed this from the top of the page:

TO SOLVE NP PROBLEMS, FIRST EXPRESS THEM IN LEAST SPACE PICTORIAL FORM. THEN PLANE THE nth dimensional picture you've created normal to its axis of radial symmetry. Keep planing until you have a bunch of simple 2d solutions to 3d problems. Then do a weighted average to arrive at certainty. Signed, a math genius PS: please don't revert without thinking about it first.

It could be useful to the article but would need writing into it rather than sitting above the main heading as it did. Cheez talk 18:24, 8 November 2007 (UTC)

[edit] Leave 'NP-complete' out of the main definition?

I am a mathematician brushing up on the definition of NP-hard (and NP-complete), and I was a bit disappointed to read the first few lines of this article. NP-hard strikes me as a more basic concept than NP-completeness, and defining the former in terms of the latter seems very confusing. You might as well say H is NP hard if L<=H for every L in P, and leave NP-complete out? Btw, this would also simplify the definition of NP-complete, by saying it is an NP-hard problem which is also in NP. (For those of you who want to discuss HP-hard for non-decision problems etc, you could do this at length in the text below the main definition for clarity.) Gaenciso (talk) 13:53, 12 December 2007 (UTC)

[edit] Please Give an Example which is NP-hard but not NPC

Seems all the examples in NP-hard are also NPC.Better examples needed.Visame (talk) 17:34, 8 February 2008 (UTC)

There's the Halting Problem, which is explicitly mentioned as such an example. Did you want one that's NP-hard, decidable, and not NP-C? LWizard @ 20:24, 8 February 2008 (UTC)

That is exactly what I want:one that's NP-hard, decidable, and not NP-C. Thanks!Visame (talk) 06:40, 13 February 2008 (UTC)

Alright, I put in TQBF. It's not technically proven outside of NP-C, but almost certainly is. If you really need a sure-thing example, you can check the articles on larger complexity classes for complete problems, or just go with regular expression inequivalence over union, concatenation, asteration, and squaring. LWizard @ 10:24, 13 February 2008 (UTC)