Timeline for Polynomially many instances imply a polynomial reduction?
Current License: CC BY-SA 4.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 11, 2023 at 16:27 | vote | accept | NL1992 | ||
| Feb 11, 2023 at 7:20 | comment | added | D.W.♦ | @NL1992, yes, that sounds right to me. As a heuristic, if you have found a Cook reduction, then my guess is that with more work it will likely be possible to find a many-one reduction. | |
| Feb 10, 2023 at 20:17 | comment | added | NL1992 | Thank you for the elaborate explanation. Each of my polynomially many instances can be constructed polynomially. It seems like I do have a Cook reduction in my case, and the language is in NP. If I understood the other sources you linked to correctly, I cannot conclude that this is NPC unless I have some special properties of the language I’m dealing with? Also, if this problem is in P, it still proves that P=NP. So perhaps at least that is something useful I can say. | |
| Feb 9, 2023 at 19:47 | history | answered | D.W.♦ | CC BY-SA 4.0 |