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 | |
|---|---|---|---|---|---|
| Jul 12, 2010 at 23:56 | comment | added | Emil | @shreevatsa: Ah, I think I see your point now. | |
| Jul 12, 2010 at 23:48 | comment | added | shreevatsa | The problem you quoted is a decision problem in NP, but it is not the same as Problem 2. (It's the same as "Decide if the input is a graph that is 3-colorable", and hence the same as Problem 1. Problem 2 may be easier.) You've changed the problem to a decision problem (by broadening the set of NO instances to include graphs that don't satisfy the condition), and the new decision problem is in NP. This is what I wrote in the last paragraph above. It's all a matter of definitions, nothing deep. | |
| Jul 12, 2010 at 23:22 | comment | added | Emil | OK, so I can phrase Problem 2 as: "Decide if the input string represents a graph that satisfies NC and is 3-colorable." | |
| Jul 12, 2010 at 23:12 | comment | added | shreevatsa | Yes, the problem "given a planar graph, decide if it is 3-colorable" is a promise problem, under the usual definitions. A decision problem is one in which all string are either YES or NO. (The problem "Decide if the input string represents a planar and 3-colorable graph" is a decision problem.) | |
| Jul 12, 2010 at 22:48 | comment | added | Emil | Well a decision problem is just one with a yes/no answer, surely? Consider the following problem: Let G be a planar graph. Decide if G is 3-colorable. Is this a promise problem? | |
| Jul 12, 2010 at 22:42 | comment | added | shreevatsa | I have already said why not, in the first paragraph: NP is a class of decision problems, not promise problems. So it is not meaningful to talk of whether Problem 2 is in NP or not, because it's not a decision problem but a promise problem (in Promise-NP). That's all there is to it. | |
| Jul 12, 2010 at 22:21 | comment | added | Emil | @shreevasta: Well, your last paragraph now is quite muddled. If you don't believe Problem 2 to be in NP, then please explain why not. Bear in mind that NC is a necessary condition, so the set of "yes" answers for Problem 2 is the same as that for Problem 1. | |
| Jul 12, 2010 at 21:47 | comment | added | shreevatsa | Sorry for the confusion; I've rewritten the answer completely. Rune's answer and comments are completely right. | |
| Jul 12, 2010 at 21:45 | history | edited | shreevatsa | CC BY-SA 2.5 |
rewrite
|
| Jul 12, 2010 at 20:55 | comment | added | Rune | @shreevatsa: The union of YES and NO instances is not the set of all graphs, it's the set of all graphs satisfying NC. Thus the problem is still a promise problem (unless NC is a trivial condition satisfied by all graphs). | |
| Jul 12, 2010 at 20:34 | comment | added | Emil | @shreevatsa: could you edit your answer then? | |
| Jul 12, 2010 at 20:00 | comment | added | shreevatsa | Oh sorry, I didn't realise that your condition is one necessary for 3-colorability. Technically, NP is a class of languages: sets of strings. What is the set of YES instances for your problem 2? It seems the only reasonable definition would be simply the set of 3-colorable graphs, in which case yes, your problem 2 is in NP, because (as a language) it's the same as Problem 1. | |
| Jul 12, 2010 at 19:30 | comment | added | Steven Stadnicki | I'm still confused by this myself (and sadly, I don't have a postscript reader handy to check out the reference). Wikipedia explicitly says 'There may be inputs which are neither yes or no. If such an input is given to an algorithm for solving a promise problem, the algorithm is allowed to output anything.' PlanetMath says something similar; it seems like the promise version of a problem can never be more complex than the non-promise version (just ignore the promise!). I'd prefer to say that his problem 2 is surely in NP but not at all guaranteed to be NP-complete. | |
| Jul 12, 2010 at 19:01 | comment | added | Emil | Response to edit: Remember that NC is a necessary condition - in other words, all 3-colorable graphs satisfy NC. For Problem 2, the succinct certificate is an explicit 3-coloring, and this certificate also guarantees that NC is satisfied. (I am not sure the survey paper discusses this situation - could you give me a paragraph reference if it does?) | |
| Jul 12, 2010 at 18:33 | history | edited | shreevatsa | CC BY-SA 2.5 |
clarify
|
| Jul 12, 2010 at 18:10 | comment | added | Emil | Thanks for answering, but you haven't given any specific reason why Problem 2 is not in NP. Would you be able to explain why you think it is not? | |
| Jul 12, 2010 at 17:57 | history | answered | shreevatsa | CC BY-SA 2.5 |