most recent 30 from http://mathoverflow.net 2013-05-25T22:45:05Z http://mathoverflow.net/feeds/question/41915 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/41915/np-hard-solution-question joseph 2010-10-12T15:51:31Z 2010-10-13T03:32:03Z

<p>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)?</p> <p>Thanks for answers </p>

http://mathoverflow.net/questions/41915/np-hard-solution-question/41916#41916 Jim Conant 2010-10-12T16:11:17Z 2010-10-12T16:11:17Z

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

http://mathoverflow.net/questions/41915/np-hard-solution-question/41930#41930 Ross Churchley 2010-10-12T18:34:33Z 2010-10-12T18:34:33Z

<p>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 <em>certified</em> by a proper 3-colouring.</p> <p>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 <em>witness</em>) 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).</p> <p>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.</p> <p>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$?").</p>