1
$\begingroup$

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

$\endgroup$
4
  • $\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$ Oct 13, 2010 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$ Oct 13, 2010 at 11:48
  • $\begingroup$ @David Speyer: You can expect anything you want, it is just your expectation:) $\endgroup$
    – joseph
    Oct 13, 2010 at 18:43
  • $\begingroup$ and moreover, I am looking for that error that I have not found yet:) $\endgroup$
    – joseph
    Oct 13, 2010 at 19:03

2 Answers 2

9
$\begingroup$

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$?").

$\endgroup$
3
  • $\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, 2010 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$ Oct 13, 2010 at 11:41
  • $\begingroup$ I suspect he's trying to solve partition. $\endgroup$ Oct 14, 2010 at 3:02
3
$\begingroup$

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."

$\endgroup$
3
  • 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$ Oct 12, 2010 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, 2010 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, 2010 at 22:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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