Do I need to consider instance restrictions when showing a language is in P?
Clash Royale CLAN TAG#URR8PPP
$begingroup$
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?
turing-machines time-complexity terminology
$endgroup$
add a comment |
$begingroup$
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?
turing-machines time-complexity terminology
$endgroup$
add a comment |
$begingroup$
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?
turing-machines time-complexity terminology
$endgroup$
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?
turing-machines time-complexity terminology
turing-machines time-complexity terminology
edited Mar 17 at 16:18
Jahar Mehru
asked Mar 17 at 15:35
Jahar MehruJahar Mehru
283
283
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
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.
$endgroup$
2
$begingroup$
Great answer! I've posted a follow up question here.
$endgroup$
– Florian Brucker
Mar 18 at 8:26
add a comment |
$begingroup$
The answer depends on exactly what problem you're solving.
If your goal is to produce an algorithm that correctly solves the problem on the restricted instances, then it's kind of up to you whether or not you check. It feels more robust to check the input but it's perfectly reasonable not to, and that puts you in the realm of promise problems. Here, the "user" promises that the input is valid, and you just have to determine whether the answer is yes or no.
If your goal is to produce an algorithm that decides whether the input is, e.g., a satisfiable 3CNF then, yes, you do need to check that the input has the properties it's supposed to have.
Your example of 3-colourability for acyclic graphs shows that there can be a big difference between the two approaches. Every acyclic graph is 3-colourable (even 2-colourable) so the algorithm for the promise problem is just output "yes"
. For the non-promise version, you need to check that your input is a valid graph representation, then check that the graph is acyclic, and only say "yes" if the input passes both tests.
In practical terms, most descriptions of graph algorithms tend to assume that the input is a valid encoding of a graph – it gets a bit tedious writing "Check the input is a valid encoding of a graph" as the first line of every algorithm!
$endgroup$
add a comment |
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "419"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f105692%2fdo-i-need-to-consider-instance-restrictions-when-showing-a-language-is-in-p%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
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.
$endgroup$
2
$begingroup$
Great answer! I've posted a follow up question here.
$endgroup$
– Florian Brucker
Mar 18 at 8:26
add a comment |
$begingroup$
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.
$endgroup$
2
$begingroup$
Great answer! I've posted a follow up question here.
$endgroup$
– Florian Brucker
Mar 18 at 8:26
add a comment |
$begingroup$
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.
$endgroup$
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.
edited Mar 18 at 2:03
answered Mar 17 at 16:24
Apass.JackApass.Jack
14.3k1940
14.3k1940
2
$begingroup$
Great answer! I've posted a follow up question here.
$endgroup$
– Florian Brucker
Mar 18 at 8:26
add a comment |
2
$begingroup$
Great answer! I've posted a follow up question here.
$endgroup$
– Florian Brucker
Mar 18 at 8:26
2
2
$begingroup$
Great answer! I've posted a follow up question here.
$endgroup$
– Florian Brucker
Mar 18 at 8:26
$begingroup$
Great answer! I've posted a follow up question here.
$endgroup$
– Florian Brucker
Mar 18 at 8:26
add a comment |
$begingroup$
The answer depends on exactly what problem you're solving.
If your goal is to produce an algorithm that correctly solves the problem on the restricted instances, then it's kind of up to you whether or not you check. It feels more robust to check the input but it's perfectly reasonable not to, and that puts you in the realm of promise problems. Here, the "user" promises that the input is valid, and you just have to determine whether the answer is yes or no.
If your goal is to produce an algorithm that decides whether the input is, e.g., a satisfiable 3CNF then, yes, you do need to check that the input has the properties it's supposed to have.
Your example of 3-colourability for acyclic graphs shows that there can be a big difference between the two approaches. Every acyclic graph is 3-colourable (even 2-colourable) so the algorithm for the promise problem is just output "yes"
. For the non-promise version, you need to check that your input is a valid graph representation, then check that the graph is acyclic, and only say "yes" if the input passes both tests.
In practical terms, most descriptions of graph algorithms tend to assume that the input is a valid encoding of a graph – it gets a bit tedious writing "Check the input is a valid encoding of a graph" as the first line of every algorithm!
$endgroup$
add a comment |
$begingroup$
The answer depends on exactly what problem you're solving.
If your goal is to produce an algorithm that correctly solves the problem on the restricted instances, then it's kind of up to you whether or not you check. It feels more robust to check the input but it's perfectly reasonable not to, and that puts you in the realm of promise problems. Here, the "user" promises that the input is valid, and you just have to determine whether the answer is yes or no.
If your goal is to produce an algorithm that decides whether the input is, e.g., a satisfiable 3CNF then, yes, you do need to check that the input has the properties it's supposed to have.
Your example of 3-colourability for acyclic graphs shows that there can be a big difference between the two approaches. Every acyclic graph is 3-colourable (even 2-colourable) so the algorithm for the promise problem is just output "yes"
. For the non-promise version, you need to check that your input is a valid graph representation, then check that the graph is acyclic, and only say "yes" if the input passes both tests.
In practical terms, most descriptions of graph algorithms tend to assume that the input is a valid encoding of a graph – it gets a bit tedious writing "Check the input is a valid encoding of a graph" as the first line of every algorithm!
$endgroup$
add a comment |
$begingroup$
The answer depends on exactly what problem you're solving.
If your goal is to produce an algorithm that correctly solves the problem on the restricted instances, then it's kind of up to you whether or not you check. It feels more robust to check the input but it's perfectly reasonable not to, and that puts you in the realm of promise problems. Here, the "user" promises that the input is valid, and you just have to determine whether the answer is yes or no.
If your goal is to produce an algorithm that decides whether the input is, e.g., a satisfiable 3CNF then, yes, you do need to check that the input has the properties it's supposed to have.
Your example of 3-colourability for acyclic graphs shows that there can be a big difference between the two approaches. Every acyclic graph is 3-colourable (even 2-colourable) so the algorithm for the promise problem is just output "yes"
. For the non-promise version, you need to check that your input is a valid graph representation, then check that the graph is acyclic, and only say "yes" if the input passes both tests.
In practical terms, most descriptions of graph algorithms tend to assume that the input is a valid encoding of a graph – it gets a bit tedious writing "Check the input is a valid encoding of a graph" as the first line of every algorithm!
$endgroup$
The answer depends on exactly what problem you're solving.
If your goal is to produce an algorithm that correctly solves the problem on the restricted instances, then it's kind of up to you whether or not you check. It feels more robust to check the input but it's perfectly reasonable not to, and that puts you in the realm of promise problems. Here, the "user" promises that the input is valid, and you just have to determine whether the answer is yes or no.
If your goal is to produce an algorithm that decides whether the input is, e.g., a satisfiable 3CNF then, yes, you do need to check that the input has the properties it's supposed to have.
Your example of 3-colourability for acyclic graphs shows that there can be a big difference between the two approaches. Every acyclic graph is 3-colourable (even 2-colourable) so the algorithm for the promise problem is just output "yes"
. For the non-promise version, you need to check that your input is a valid graph representation, then check that the graph is acyclic, and only say "yes" if the input passes both tests.
In practical terms, most descriptions of graph algorithms tend to assume that the input is a valid encoding of a graph – it gets a bit tedious writing "Check the input is a valid encoding of a graph" as the first line of every algorithm!
answered Mar 17 at 18:11
David RicherbyDavid Richerby
70.4k16107196
70.4k16107196
add a comment |
add a comment |
Thanks for contributing an answer to Computer Science Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f105692%2fdo-i-need-to-consider-instance-restrictions-when-showing-a-language-is-in-p%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown