Hello, i have NP hard problem. Let imagine I have found some polynomial algorithm that find ONLY one of many existing solutions of that problem, but at least one solution (if present in the probem). Is that algorithm considered as solution of NP=P question (if that algorithm transformed to mathematical proof)?

Thanks for answers

  • $\begingroup$ Someone should tell you that the overwhelming likelihood is that there is an error in your algorithm. You have stated the question correctly: If you find a polynomial time algorithm which takes a list of n integers and finds a partition into two parts of equal sum, assuming such a partition exists, then you have shown P=NP. And it is fine to take the list to already be sorted, or to only find one of many possible partitions. $\endgroup$ – David E Speyer Oct 13 '10 at 11:46
  • $\begingroup$ I expect you have an error because: (1) the general belief is that $P \neq NP$ and (2) your questions don't make you sound like someone with enough experience to find an algorithm which brilliant algorithmists have looked for over several decades. Obviously, these are superficial ways to judge, but it is worth knowing that there is probably some flaw in the algorithm. $\endgroup$ – David E Speyer Oct 13 '10 at 11:48
  • $\begingroup$ @David Speyer: You can expect anything you want, it is just your expectation:) $\endgroup$ – joseph Oct 13 '10 at 18:43
  • $\begingroup$ and moreover, I am looking for that error that I have not found yet:) $\endgroup$ – joseph Oct 13 '10 at 19:03

For concreteness, let's pick an NP-hard problem to talk about. Given a graph $G$, the 3-colouring problem asks: "can the vertices of $G$ be painted by three colours such that for any edge $uv$, $u$ and $v$ get different colours?" This is a decision problem --- its possible answers are "yes" or "no" --- but a "yes" answer can be certified by a proper 3-colouring.

Say you had a polynomial-time algorithm that found, for any input graph, a proper 3-colouring if one exists. Then your algorithm would solve the 3-colouring problem: it answers "yes" or "no" correctly, and even gives a nice certificate (or witness) of a "yes" answer. This would be enough to show that P=NP. It is not necessary to find all possible 3-colourings (indeed, there may be exponentially many of them).

Now, if you had some sort of "partial algorithm," which solves an NP-hard problem only for some specific instances, then this is not enough. For example, the 3-colouring problem can be easily solved for bipartite graphs, split graphs, and more. The reason for this is that the restriction of an NP-hard problem is not necessarily NP-hard.

Finally, just to elaborate on Jim's answer: many popular descriptions of NP-hard problems, like Travelling Salesman, don't sound like decision problems. But they are, really: they can be retranslated as a series of questions with yes or no answers (e.g. "does there exist a travelling salesman route of length at most $x$?").

| cite | improve this answer | |
  • $\begingroup$ I am solving if it is possible to divide set of Z numbers to two groups with same value. only thing that is specific is, that I need to order numbers from smallest to highest. $\endgroup$ – joseph Oct 12 '10 at 22:38
  • $\begingroup$ Sorting a set of n numbers only takes n log n steps, so you can do that in preprocessing without effecting whether your algorithm is polynomial. $\endgroup$ – David E Speyer Oct 13 '10 at 11:41
  • $\begingroup$ I suspect he's trying to solve partition. $\endgroup$ – Suresh Venkat Oct 14 '10 at 3:02

By definition, an NP hard problem must be a decision problem. That means it must have an answer of "yes" or "no," based on any given input. So it can't have "multiple answers."

| cite | improve this answer | |
  • 2
    $\begingroup$ The OP was asking whether it was ok to find ANY accepting solution, which is of course fine. An NP-hard problem can indeed have multiple witnesses that establish a YES answer. $\endgroup$ – Suresh Venkat Oct 12 '10 at 17:26
  • $\begingroup$ Suresh, I completely agree with what you've said. But joseph's question is not phrased that way. $\endgroup$ – Jim Conant Oct 12 '10 at 19:32
  • $\begingroup$ I am not english speaking, and now, when I get another view, I must change acceptation of best answer $\endgroup$ – joseph Oct 12 '10 at 22:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.