Timeline for Decision problem restricted to inputs that satisfy some necessary condition.
Current License: CC BY-SA 2.5
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 15, 2020 at 7:27 | history | edited | CommunityBot |
Commonmark migration
|
|
| Jul 13, 2010 at 16:44 | comment | added | shreevatsa | Yes, Goldreich touches on this issue in 1.1 (top of p.3) of his survey. The point is that when the condition can be checked in the class of interest, there is a natural conversion to a decision problem, and it does not matter much. Planarity testing (or testing whether the input is a graph) ∈ P, so when the class of interest is NP (as in Garey and Johnson), it's fine to treat it as a decision problem. But when working with some restricted class in which planarity testing isn't, it's more meaningful and common to consider it a promise problem—same here. Anyway, just a matter of conventions. :-) | |
| Jul 13, 2010 at 15:01 | comment | added | Emil | @shreevasta: Well Garey and Johnson stated all their problems like "INPUT: A graph G" etc. It is the normal way to state decision problems. | |
| Jul 13, 2010 at 14:36 | comment | added | shreevatsa | "So by convention, Problem 3 means the following" — not really. That's just a transformation, used only if you want to force it to be a decision problem. Another equally useful (and more common?) convention is to take it as stated, a promise problem. As you observed yourself, the former is not always useful. Rune's answer below implicitly assumes the latter convention, because, well, that's how your problem 2 is stated. :- | |
| Jul 13, 2010 at 11:47 | history | edited | Emil | CC BY-SA 2.5 |
Added what I think is an answer
|
| Jul 12, 2010 at 23:54 | history | edited | Emil | CC BY-SA 2.5 |
removed comment at the end
|
| Jul 12, 2010 at 22:30 | history | edited | Emil | CC BY-SA 2.5 |
commented on two answers
|
| Jul 12, 2010 at 20:40 | comment | added | Emil | @Antonio: No, we do not know if determining NC is in NP. I'm not sure that trusting the promise is an issue, because NC is a necessary condition. | |
| Jul 12, 2010 at 20:14 | answer | added | Rune | timeline score: 1 | |
| Jul 12, 2010 at 19:09 | comment | added | Antonio E. Porreca | Emil, can NC be determined in nondeterministic polytime? If so (as in the NC = 3-colourability example) then it seems to me that Problem 2 does belongs to NP: just ignore the “promise” or any NC certificate given as input, and recheck the property before testing 3-colourability. On the other hand, if NC is too hard (e.g., NEXPTIME-complete) you have to “trust” the promise, because you don’t have the time to verify it (and the problem is not in NP). | |
| Jul 12, 2010 at 17:57 | answer | added | shreevatsa | timeline score: 1 | |
| Jul 12, 2010 at 16:52 | comment | added | Emil | Just to clarify, my comment was in respone to Mariano's first comment. | |
| Jul 12, 2010 at 16:51 | comment | added | Emil | Mariano: Yes the NC might be that. In this case Problem 2 is trivial, and so in NP. | |
| Jul 12, 2010 at 16:51 | comment | added | Mariano Suárez-Álvarez | or, to satisfy your "(but not sufficient)" let NC be "is $3$-colorable or isomorphic to the complete graph in three vertices". | |
| Jul 12, 2010 at 16:50 | comment | added | Suresh Venkat | this is indeed a promise problem. These are common in approximation lower bounds, where you supply a set of inputs that are promised to have either a large or small value for some function, and the problem is to separate them. | |
| Jul 12, 2010 at 16:48 | comment | added | Mariano Suárez-Álvarez | You cannot say that problem $2$ is in NP, because the condition NC might me "is $3$-colorable"! | |
| Jul 12, 2010 at 16:44 | history | asked | Emil | CC BY-SA 2.5 |