Timeline for Reconciling NP and the decision problem
Current License: CC BY-SA 3.0
Post Revisions
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 21, 2016 at 6:16 | comment | added | SamTheTomato | Thanks. I should note that I have zero background in computer science, but work in a field that overlaps slightly, so I'm sorry if my question was trivial. | |
| May 20, 2016 at 21:55 | comment | added | BlueRaja - Danny Pflughoeft | Related: Why isn't this undecidable problem in NP? | |
| May 20, 2016 at 20:03 | vote | accept | SamTheTomato | ||
| May 20, 2016 at 19:35 | history | tweeted | twitter.com/StackCompSci/status/733743056533458944 | ||
| May 20, 2016 at 19:15 | comment | added | Raphael | You need to read more carefully: we don't check the solution but a certificate for the answer. That can but does not have to be a solution of the associated computation/optimization problem (if there is indeed one) but it does not have to be. | |
| May 20, 2016 at 19:14 | comment | added | Raphael | Welcome to Computer Science! Your question is a very basic one. Let me direct you towards our reference questions which cover some fundamentals you seem to be missing in detail. Please work through the related questions listed there, try to solve your problem again and edit to include your attempts along with the specific problems you encountered. Good luck! | |
| May 20, 2016 at 18:37 | comment | added | ShreevatsaR | In your example, "given a particular solution" means "given a max cut of size at least k" -- it does not mean "given the string YES" or anything like that. Once you are given the solution (more commonly called certificate or witness), you only need to be able to check that the witness is indeed a witness, e.g. in your case check that what you're given is indeed a max cut of size ≥ k. You don't have to find a max cut. | |
| May 20, 2016 at 16:51 | answer | added | Yuval Filmus | timeline score: 14 | |
| May 20, 2016 at 16:40 | answer | added | Joey Eremondi | timeline score: 6 | |
| May 20, 2016 at 14:27 | history | asked | SamTheTomato | CC BY-SA 3.0 |