Talk:NP-hard

From Wikipedia, the free encyclopedia

You have new messages (last change).

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

[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)
Retrieved from "http://en.wikipedia.org../../../n/p/-/Talk%7ENP-hard_342b.html"