patternMinor
Do I need to consider instance restrictions when showing a language is in P?
Viewed 0 times
restrictionsshowingneedconsiderlanguageinstancewhen
Problem
I have already shown that 3-colorable for an unrestricted graph is in NP, but I was thinking about the similar language defined as the set of all acyclic $G$, where $G$ such that $G$ is 3-colorable. In my proposition of an algorithm in P, I wasn't sure if my algorithm needs to verify that $G$ indeed contains no cycle or if I assume all inputs are instances of this language (assume all inputs are acyclic graphs). In general, I was wondering if my algorithm has to decide whether the input is of the desired instance ON TOP OF actually showing the properties of the language can be done in polynomial time. I'm still learning so I am confused about this part and this has been bugging me for a while.
If this question is too confusing, consider 3SAT. Must I show that verifying the input is indeed a 3CNF is in P to conclude, or can I assume we are only considering inputs within an instance?
If this question is too confusing, consider 3SAT. Must I show that verifying the input is indeed a 3CNF is in P to conclude, or can I assume we are only considering inputs within an instance?
Solution
I was wondering if my algorithm has to decide whether the input is of the desired instance ON TOP OF actually showing the properties of the language can be done in polynomial time.
Very nice question!
What you are talking about is best characterized as promise problem, "a generalization of a decision problem where the input is promised to belong to a particular subset of all possible inputs". The conventional way to handle promise problem is there are no requirements on the output if the input does not belong to the promise. In particular, if you want to show a promise problem is in P of promise problems, your algorithm do not need to check whether the input is valid or not and your algorithm can behave arbitrarily if the input is invalid.
For an in-depth educational survey on promise problems, you are encouraged to read Oded Goldreich's exposition On Promise Problems, July 11, 2005.
However, if you want to show a promise problem is in P, your algorithm must check whether the input is valid or not and, if the input is invalid, a.k.a as a noninstance, output 0. Here P stands for the complexity class as in the famous P versus NP problem, a.k.a. P of decision problems, i.e. PTIME or DTIME$(n^{O(1)})$ as defined at Wikipedia, or the complexity class P as defined in section 34.1 Polynomial time of the popular textbook introduction to algorithm by CLRS, version 3.
Take 3SAT for an example. An algorithm that show 3SAT is in P (of decision problems) should check whether the input is a formula in conjunctive normal form each of whose clauses contains at most three literals among other restrictions. The algorithm should output 0 if it finds the input is not a valid instance of 3SAT.
It is easy to check whether a problem instance is a valid instance or not for almost all decision problems people have been interested in. It is so easy and so common that people have become so sloppy or efficient that this verification step is usually skipped or even forgotten in the specification of an algorithm. That might be the source of your confusion.
I would recommend beginners to write clearly this verification step for the first few occasions before joining the common practice.
Very nice question!
What you are talking about is best characterized as promise problem, "a generalization of a decision problem where the input is promised to belong to a particular subset of all possible inputs". The conventional way to handle promise problem is there are no requirements on the output if the input does not belong to the promise. In particular, if you want to show a promise problem is in P of promise problems, your algorithm do not need to check whether the input is valid or not and your algorithm can behave arbitrarily if the input is invalid.
For an in-depth educational survey on promise problems, you are encouraged to read Oded Goldreich's exposition On Promise Problems, July 11, 2005.
However, if you want to show a promise problem is in P, your algorithm must check whether the input is valid or not and, if the input is invalid, a.k.a as a noninstance, output 0. Here P stands for the complexity class as in the famous P versus NP problem, a.k.a. P of decision problems, i.e. PTIME or DTIME$(n^{O(1)})$ as defined at Wikipedia, or the complexity class P as defined in section 34.1 Polynomial time of the popular textbook introduction to algorithm by CLRS, version 3.
Take 3SAT for an example. An algorithm that show 3SAT is in P (of decision problems) should check whether the input is a formula in conjunctive normal form each of whose clauses contains at most three literals among other restrictions. The algorithm should output 0 if it finds the input is not a valid instance of 3SAT.
It is easy to check whether a problem instance is a valid instance or not for almost all decision problems people have been interested in. It is so easy and so common that people have become so sloppy or efficient that this verification step is usually skipped or even forgotten in the specification of an algorithm. That might be the source of your confusion.
I would recommend beginners to write clearly this verification step for the first few occasions before joining the common practice.
Context
StackExchange Computer Science Q#105692, answer score: 7
Revisions (0)
No revisions yet.