Talk:NP-hardness

Untitled

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:

• http://www-math.mit.edu/~spielman/AdvComplexity/1998/lect1.ps
• http://www.cs.wisc.edu/~jyc/830Lecturenotes/Lecture24.ps
• http://www.maths.ox.ac.uk/~talbot/handouts/lec4hand.ps

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 Seriously, I think the opening paragraph broke my brain. —Preceding unsigned comment added by 130.215.185.82 (talk) 19:27, 13 May 2011 (UTC)

Ha! Explanations on a technical wikipedia article!?! Blasphemy! Let's be honest, despite the centrality of this topic to the field, it's hopelessly pedantic and convoluted. It's a wonder that computer scientists are able to tie their shoes in the morning (I suspect that many use slip-ons). The second I read that NP-Hard problems didn't have to be NP, I gave up. What an idiotic name! And the letter P is used to represent both 'Polynomial time' AND 'Problem'? So, that means it is legal and correct to say 'A P that is NP-Hard is neither P nor NP'?

These people are hopeless.

107.3.37.113 (talk) 11:46, 18 March 2013 (UTC)

---

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 m^k time or whatever. Poor Yorick

============================================================

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.

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. ^L_Wizard @ 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] ^L_Wizard @ 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 ^L_Wizard @ 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. ^L_Wizard @ 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. ^L_Wizard @ 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? ^L_Wizard @ 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)

Impossible to understand

This page is almost incomprehensible due to the style of writing and the lack of attention to explaining the diagrams. The Euler diagrams essentially looks similar with no clear description. A diagram is supposed to support the text and make the concept clearer. This is clearly not the case here.

Can someone help the author fix this PLEASE! 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)

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. ^L_Wizard @ 23:34, 27 March 2007 (UTC)

Something seems very wrong with this example. The proof reduces SAT to HALT, thus saying that if we can solve HALT we can solve SAT. While this may be true, the method seems highly contrived. SAT is already a decidable problem, and the method in which it reduces to HALT is by arbitrarily adding an infinite loop to the false state of the SAT problem so that it no longer returns a solution in some cases, which would mean this is no longer an actual SAT problem. If this is acceptable then this same proof method could be used on any decision problem, thus even the most basic problem in P can then be reduced to HALT by adding that same infinite loop to the false state. Is their really any utility in a proof that says if we can decide an undecidable function, we can then decide any already decidable function? ABenYouCanTrust (talk) 20:37, 24 October 2011 (UTC)

The method is correct and can indeed be used to show that any decidable problem can be reduced to the halting problem. I think this example should be kept because it makes clear the difference between NP-hard and NP-complete. Moreover, the halting problem is well known, so it will be understood by many readers with a minimal background in computability theory. But I agree with you that the question whether a problem in NP can be reduced to SAT is not very natural, as the answer is rather trivial. Pintoch (talk) 20:49, 20 April 2014 (UTC)

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)

Hey there is something weird in this article. It says: "Decision problems that are both NP-hard and NP-easy, but not necessarily in NP" as definition for NP-equivalent Problems. Now it is truly puzzling how a Problem could be NP-equivalent without being in NP. That's why I went to the linked article for NP-equivalent problems, but that was even less helpful, because while it says here NP-equivalent Problems are decision problems it says in the article on NP-equivalence, that those are function problems. So I figured one of these articles must be wrong in at least that aspect. Yosoth (talk) 12:29, 1 November 2022 (UTC)

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)

Exactly, this is about Computational Complexity, which is very different from complex behaviour in nature leading to emergent properties, I'm changing the link from Irreducible complexity (Emergence) from here to emergence. --Dunx 18:54, 14 Dec 2013 (GMT)

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.

Sci.Am., "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)

LMAO. Well, actually, I don't think that assumption's all that obvious to be making. Maybe if we changed the actual integers in the subset problem to all positive, and check if they summed to fifteen (for instance) - instead of confusing readers not familiar with negative numbers. 220.224.246.97 (talk) 22:18, 5 June 2013 (UTC)

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)

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)

I quite agree with you, Gaenciso. Pintoch (talk) 20:54, 20 April 2014 (UTC)

It's in fact causing a circular definition. I tried to get a refresher on what NP-complete is, where it says:

A decision problem L is NP-complete if it is in the set of NP problems and also in the set of NP-hard problems.

So I came here to refresh the details on what a NP-hard problem is, just to find that:

A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H

Someone please change at least one of these to eliminate the circularity. --pgimeno (talk) 18:15, 13 May 2014 (UTC)

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? ^L_Wizard @ 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. ^L_Wizard @ 10:24, 13 February 2008 (UTC)

Alas, I am also confused by this question and I think the present TQBF example isn't satisfactory. There is a very definitive statement to the effect: "not all decidable problems are NP", but then as an illustration you are saying "here is a decidable problem which is probably not NP". So the reader is left wondering whether the first statement should have been "it is believed that not all decidable problems are NP", or "one can prove that not all ..., but specific examples are unknown", or "there are known examples but too complex to describe them here". Right now this paragraph is almost self-contradictory :) Your post above appears to suggest that it is one of the two last cases, but I probably know too little to understand what the "reqular expression inequivalence" was meant to mean. So I am suggesting at least to spell out what is known and what is only believed to be true.

As to the halting problem -- really, that's way too different. Decidable problems matter to usual people. Undecidable problems are, after all, a fathom invented to feed the imagination of computer scientists. It's an important tool, but only the decidable problems matter in real life, and knowing there is a "real" problem more difficult than NP-hard is bound to bear practical consequence, even if hard to quantify.

(BTW, once TQBF is mentioned in this context, it would be nice to mention somewhere inside the main TQBF article that it is believed to be outside NP... something like a clear explanation and maybe even literature refs?) 72.134.22.246 (talk) 08:05, 25 September 2009 (UTC)

NP-hard problem don't need to be decision problems. Thus there are NP-hard problems like #SAT (count the number of satisfying assignments), etc. which cannot be NPC. If you want decision problems, then any problem which is EXPSPACE-complete or 2-EXPTIME-complete is NP-hard but provably not NPC. --Robin (talk) 14:07, 25 September 2009 (UTC)

Quintuple negative, impressive!

But not all NP-Hard problems that aren't NP-Complete are undecidable.

Maybe there is a clearer way of saying this. --128.32.45.173 (talk) 01:35, 9 April 2009 (UTC)

Thank you for the praise. I've reworded it. ^L_Wizard @ 07:22, 9 April 2009 (UTC)

Those Euler diagrams

I find the two Euler diagrams – or at least, the one on the left – impossible to understand. Does the label "NP" refer to the whole diagram, or the the region outside the three convex curves? Does the label "NP-Hard" refer to the whole large ellipse, or just the part of it outside the circle? Does the label "NP-Complete" refer to the intersection of the circle and the large ellipse, or to more than this? Maproom (talk) 20:52, 19 March 2010 (UTC)

I retract the above. The diagrams now seem perfectly clear. I guess I hadn't had enough coffee that day. Maproom (talk) 09:14, 30 July 2010 (UTC)

VERY Important point: Heuristics Exist To Resolve Many NP-hard Problems

IMO, it is VERY important to make clear that for many NP-hard or NP-complete problems, heuristic algorithms exist that will either give a "good" solution or the exact solution quickly in many cases - but which will fail in some cases. The KEY POINT from a "general understanding" perspective is that any algorithm that is guaranteed to find the exact solution in all cases will be slow. Without this information being in the article, a high proportion of people who read it will be mislead. Does anybody disagree? New Thought (talk) 21:18, 29 July 2010 (UTC)

You are right, that's why I just added a few words on FPTAS, PTAS and APX in the Consequences section (perhaps even more words should be said though).EXPTIME-complete (talk) 00:32, 6 March 2017 (UTC)

"if and only if" - easily misunderstood?

Given if and only if is used in the very beginning of the introduction and doesn't mean exactly what a "casual reader" would think, maybe there's a way to rewrite or complement the sentence ("A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H") to make it more readable to us who only have a vague understanding of the concepts of P, NP, NP-complete and NP-hard?

I navigated from P versus NP problem to NP-complete to NP-hard to quickly refresh my understanding of the relationships between the complexity classes and while I found the the first statements of the introduction of the NP-complete page to be very clear and sufficient, this introduction was easily misunderstood if I hadn't noticed the link behind if and only if. While these are pretty complex topics and requires background knowledge I think it's generally a good thing to try to have the introduction and especially the first few statements as easy to grasp as possible (while still accurate and precisely defined), don't you?

The usage of if and only if requires knowledge of a term I don't think is too commonly used to denote this kind of logical relationship when adressing a broader audience..? Even as a programmer having studied quite a lot of mathematics it was news to me at least. Anyway, long story for a small suggestion. This is not my expertise so I don't wan't to touch a well crafted article so I'm just making a suggestion instead: If you want to keep the strict language used, maybe you could complement with a clarification, along the lines with "if and only if (which in the field of mathematics means ...)" for example?

83.227.152.68 (talk) 16:51, 9 August 2010 (UTC)

Examples and the TSP

It says on the article : "Another example of an NP-hard problem is the optimization problem of finding the least-cost cyclic route through all nodes of a weighted graph. This is commonly known as the Traveling Salesman Problem. There are also decision problems that are NP-hard but not NP-complete" - but the TSP problem is not NP-Complete, it's just NP-Hard. Maybe you could remove the "also" from the text, or reorder it. The way it is, it gives the impression that TSP is NP-Complete. --Wladston (talk) 21:51, 15 November 2010 (UTC)

Done. ^L_Wizard @ 04:28, 16 November 2010 (UTC)

Euler diagram wrong.

I'm removing the Euler diagram for reasons I've spelled out on its discussion page. Twin Bird (talk) 23:09, 23 July 2011 (UTC)

I re-removed it because it came back. To summarize the problem the trivial languages ∅ and Σ* are in both P and NP. However, they are not NP-complete even if P=NP. The right-hand diagram incorrectly states that, if P=NP, then P=NP=NP-complete but the two trivial languages are a counterexample to this claim. Dricherby (talk) 17:24, 31 January 2016 (UTC)

Not sure if useful or worth mentioning, but I have seen some complexity theory sources use a formal definition of language that explicitly excludes the two trivial languages from consideration. That is, the trivial languages are never contained in any complexity class and statements like "all languages" and "some language" always refer to non-trivial languages automatically. This is done precisely to allow "more elegant" statements like "if P=NP, then P=NP=NP-complete, and all languages are NP-hard" instead of "if P=NP, then P=NP="NP-complete plus the trivial languages", and all non-trivial languages are NP-hard". — Preceding unsigned comment added by 190.229.37.164 (talk) 16:09, 6 July 2017 (UTC)

Circular Definitions

The definition given here says that "A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H (i.e., L ≤ TH). In other words, L can be solved in polynomial time by an oracle machine with an oracle for H." This defines NP-hard in terms of NP-complete (essentially saying NP-hard includes anything that effectively reduces some NP-complete problem to a P one) But the intro to the NP-complete article says "A decision problem L is NP-complete if it is in the set of NP problems and also in the set of NP-hard problems". This may be true but it is pretty useless as either a definition or an explanation. My uninformed guess is that what you want to say is that NPH includes *any* problem whose solution can be used to solve any NP problem in poly time and that NPC is the subset of NPH problems that are actually themselves in NP.

If that's right then what I'd say in the intro here is something like "A problem H is NP-hard if and only if every NP problem is polynomial time Turing-reducible to H." And on the other page I'd say "A decision problem L is NP-complete if it is in the set of NP problems and can be used to resolve any other NP problem in only polynomial additional time. (Problems with the latter property are called NP-Hard so NPC is just the intersection of NPH with NP itself)"

Of course it follows that H2 is guaranteed to be NPH if there is some H1 in NPH which is reducible to H2 and in particular if there is an NPC problem which is so reducible (but I'm not sure about the "only if" unless we know that NPC is nonempty)

P.S. This complaint appears to have been made by someone else (user Gaenciso)almost 5 years ago (in Dec 2007), so I won't hold my breath waiting for a fix! alQpr (talk) 02:22, 5 July 2013 (UTC)

I agree. Let me try to fix this. -- Pintoch (talk) 15:36, 31 July 2014 (UTC)

Misleading statement

From the article:

If P ≠ NP, then NP-hard problems cannot be solved in polynomial time, while P = NP does not resolve whether the NP-hard problems can be solved in polynomial time;

The second part is misleading because it is known that there exist NP-hard problems that are not in P, namely those in EXPTIME or harder. The only part P=NP wouldn't resolve is whether there exist NP-hard problems that are not in PSPACE or in EXPTIME. It wouldn't even make sense to say "P = NP wouldn't resolve whether any NP-hard problems can be solved in polynomial time", because in fact it would resolve it for NP-complete problems, which is exactly the class of NP-hard problems which can be solved in polynomial time.

I'll remove the part of sentence. -- 80.152.204.232 (talk) 13:55, 5 June 2015 (UTC)

Naming convention issue

From the article:

NP

Class of computational problems for which a given solution can be verified as a solution in polynomial time by a non-deterministic Turing machine.:

As far as I understand, a problem is in NP if it can either be verified in polynomial time by a deterministic machine or, equivalently, solved in polynomial time by a non-determistic one. I think this sentence is confusing the two definitions, maybe it can be clarified. Ksarnek (talk) 10:11, 6 April 2016 (UTC)

Cryptography and NP-harness

Hi,

The article mentions cryptography in the application areas. However, based on this Reddit thread and this Stackoverflow thread, it seems like cryptography is a widely different topic: NP-hardness discusses worst-case scenarios (e.g. how hard it is to solve this particular problem, in the worst case), where cryptography tackles average-case scenarios (e.g. how hard it is to break the system for any case).

I hence suggest removing cryptography from the list, or at least adding a footnote discussing this. What do you think? #!/bin/DokReggar -talk 09:47, 2 February 2017 (UTC)

How is NP-hard hard again?

The article speaks of a problem H that is NP-hard, saying "assuming a solution for H takes 1 unit time, we can use H‎'s solution to solve L in polynomial time" Since H takes less time than L, wouldn't that mean H is less hard than L? In what sense, then, is H "at least as hard as the hardest problems in NP"? Qwertie (talk) 13:04, 16 January 2018 (UTC)

In traditional complexity theory two problem are considered to be equivalently hard if the time to solve one is a polynomial function of the time to solve the other. So in that sense H and L are equivalently hard. Of course polynomials can be very large (e.g. x¹⁰⁰), so whether that notion of equivalence has any practical meaning, is open to question. The language of the sentence you quote could be improved; what "unit time" means here is not clear.--agr (talk) 15:14, 16 January 2018 (UTC)

Different text for picture

NP-completeness

compare it with this text - it differs in an important aspect. I dont understand it sadly so I cant correct — Preceding unsigned comment added by LasagneAlForno (talk • contribs) 01:56, 15 July 2021 (UTC)

Problem with definition

This article basically gives three definitions, the first one wrt polynomial-time many-one (Karp) reduction, the second one wrt polynomial-time Turing (Cook) reduction, and the third one wrt an unspecified kind of polynomial-time reduction, and claims the first two to be equivalent and the third one to imply the first two. This is extremely confusing. The definitions wrt Karp and Cook reductions are not equivalent, and that is not only due to the inclusion/exclusion of function problems: e.g. assume that NP != coNP then the complementary of SAT is NP-hard in the Cook sense but not in the Karp sense.

Should we give both definitions, note their difference clearly and be precise about which one we are referring to when talking about the properties of NP-hard problems? Stormraiser (talk) 16:52, 16 November 2022 (UTC)

It looks to me like the textbook definition uses many-one reductions, not Turing reductions. I verified this in two textbooks (Introduction to Algorithms and Computational Complexity: A Modern Approach). So I believe the Turing reduction definition to be simply wrong. This is also confirmed by the definitions used on the Wikipedia page for NP Completeness.

Unless there is an objection of some sort, I believe the incorrect definition should be removed. AlgorithmSoup (talk) 01:04, 12 November 2023 (UTC)

I have now also checked the original reference for the Turing-reduction based definition (the book A First Course in Computability), and the definition that the book gives (page 135 of the book) is the many-one definition. So the polynomial-time Turing definition is not correct, and the citation for it does not back it up. I am going to remove the incorrect definition. AlgorithmSoup (talk) 01:29, 12 November 2023 (UTC)

NP?

Doesn’t NP hard means the gamer has to use Nintendo Power magazine tips in order to progress through the game?

As in Nintendo Power hard?

2600:8801:0:2B10:4011:67BD:24CD:EB4D (talk) 20:05, 26 February 2023 (UTC)