Timeline for Validity of an argument for an implication of NP-Completeness
Current License: CC BY-SA 4.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 9, 2022 at 13:51 | comment | added | Manfred Weis | @VilleSalo --> therefore Fedor Petrov's question would be answered in the negative if it could be shown that his problem is NP-complete; is that argument valid? | |
| Sep 9, 2022 at 13:49 | comment | added | Manfred Weis | @VilleSalo the problem I see is that we have a constrained matching problem, which is generally NP-complete; now, knowing that a problem is NP-complete means that every instance, including those that are not acceptable, of other NP-complete problems "translate" to instances of the original (constrained matching) problem and would thus prove that not every instance of the matching problem has a solution. In my "opinion" proving the NP-completeness of a problem would therefore also prove the existence of instances without valid matching --> | |
| Sep 9, 2022 at 9:39 | comment | added | Ville Salo | A problem $P$ being NP-complete means that you can solve any NP problem using a hypothetical algorithm for $P$. An algorithm for $P$ with just positive instances is useless (it just always says "yes" no matter what you give it). So such a problem is NP-complete for Turing reductions iff P $=$ NP (for many-one reductions it is unconditionally not NP-complete). Does this solve your second question, or is it something more substantial? | |
| Sep 7, 2022 at 15:29 | history | asked | Manfred Weis | CC BY-SA 4.0 |