Mathematics desk
< March 28	<< Feb \| March \| Apr >>	March 30 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

March 29[edit]

The FNP version of every NP-complete problem is NP-hard[edit]

Hello,

The article FNP states "The FNP versions of these problems ask not only if it exists but what its value is if it does. This means that the FNP version of every NP-complete problem is NP-hard". I understand this claim intuitively, but how this can be proved? Thanks, 77.126.75.185 (talk) 19:45, 29 March 2017 (UTC)[reply]

I've taken the liberty of disambiguating the above wikilink. Loraof (talk) 21:47, 29 March 2017 (UTC)[reply]

Any instance of a decision NP-complete problem is, straightforwardly and in polynomial time, reducible to an instance of the corresponding FNP problem. This means the FNP problem is NP-hard. (Every problem in NP is polynomial-time reducible to the NP-complete problem, which is in turn polynomial-time reducible to the corresponding FNP problem.) --98.115.89.196 (talk) 01:25, 30 March 2017 (UTC)[reply]