Timeline for When is a problem strongly NP-complete
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 19, 2020 at 21:30 | comment | added | D.W.♦ | Cross-posted: cs.stackexchange.com/q/121745/755, math.stackexchange.com/q/3586812/14578. Please do not post the same question on multiple sites. | |
| Mar 19, 2020 at 20:55 | vote | accept | tala | ||
| Mar 19, 2020 at 17:30 | answer | added | D.W.♦ | timeline score: 0 | |
| Mar 19, 2020 at 14:05 | comment | added | tala | Thank you for all your comments, now I have reformulated my question. I'm still waiting for your idea | |
| Mar 19, 2020 at 14:03 | history | edited | tala | CC BY-SA 4.0 |
added 404 characters in body
|
| Mar 19, 2020 at 2:57 | comment | added | vonbrand | @tala again, this instance has a fixed answer (we might not know it, but that is besides the point). Nothing to "compute", a simple look up. "Complexity" refers to the resources needed to compute answers to problems with infinite instances (if finite, a boring lookup is all what is needed). | |
| Mar 15, 2020 at 1:14 | comment | added | tala | Okay, it's true what you said. I formulate the problem: Input: A polynomial equation on n variables whose coefficients are integers (example: $2x^3_1 x_2 + x_1x^3_3 - 3x_4 = 8$) Question: Does this equation have a solution in space {0,1}$^n$ (Can we satisfy the equation by choosing for each variable the value 0 or 1) How to prove that this diophantine equation 0/1 is strongly NP-complete? | |
| Mar 15, 2020 at 0:18 | comment | added | Steven | As @YuvalFilmus said, It makes no sense to say that "this diophantine equation is strongly NP-complete" because 1) you did not specify what decision problem you are interested in, and 2) (strong) NP-completeness only makes sense over classes of instances. The answer to any single (fixed) instance of any problem in NP can be found in constant time. | |
| Mar 14, 2020 at 14:30 | review | Close votes | |||
| Mar 31, 2020 at 3:05 | |||||
| Mar 14, 2020 at 13:24 | comment | added | tala | Thanks for your comment, NP complete is good for me! but this is a strongly NP complete. How demonstrated that this problem is strongly NP complete. | |
| Mar 13, 2020 at 18:16 | comment | added | Yuval Filmus | What does it mean for a diophantine equation to be NP-complete? NP-completeness is a category of decision problems. What decision problem do you have in mind? | |
| Mar 13, 2020 at 14:16 | history | asked | tala | CC BY-SA 4.0 |