patternMinor
Is there a formal definition of sub-instances or sub-problems?
Viewed 0 times
definitioninstancesformalsubproblemsthere
Problem
A decision problem is denoted as a language $L \subseteq \Sigma^{*}$.
For every instance $x \in \Sigma^{*}$, we say $x$ is a yes-instance if $x \in L$ and a no-instance if $x \not\in L$.
For some algorithms (e.g. devide-and-conquer, dynamic programming), we may consider some sub-instances firstly, given an instance $x$.
I want to know whether I can let the substrings or the prefixs (suffixs) of $x$ be (all of) the sub-instances.
Is there a formal definition of sub-instances?
For every instance $x \in \Sigma^{*}$, we say $x$ is a yes-instance if $x \in L$ and a no-instance if $x \not\in L$.
For some algorithms (e.g. devide-and-conquer, dynamic programming), we may consider some sub-instances firstly, given an instance $x$.
I want to know whether I can let the substrings or the prefixs (suffixs) of $x$ be (all of) the sub-instances.
Is there a formal definition of sub-instances?
Solution
I don't think there is a widely-used formal definition, and that this is so for a good reason. Sub-problems or sub-instances are tools used in the process of designing algorithms (for "divide and conquer" or "dynamic programming" in particular, but also more generally).
The process of (humans) designing algorithms is not a completely formal process: it relies on intuition and informal insight to arrive at an idea of an algorithm, and eventually refine this idea into an actual formalized algorithm.
As for your final question
I want to know whether I can let the substrings or the prefixs (suffixs) of $x$
be (all of) the sub-instances. Is there a formal definition of sub-instances?
This depends on the context. It could be that you're reading some text where someone has given a formal definition of "sub-instance". If not, then I think it is best to work under the assumption that there is no formal definition of "sub-instance" here.
Given that "sub-instance" is only an informal notion, how do you determine whether something is a sub-instance? The only option is to try it out and see if it works. The idea of something being a sub-instance is equally valid as the idea that it isn't a sub-instance. What you need to do is to determine which of the two ideas is more useful in constructing or reasoning about an algorithm.
The process of (humans) designing algorithms is not a completely formal process: it relies on intuition and informal insight to arrive at an idea of an algorithm, and eventually refine this idea into an actual formalized algorithm.
As for your final question
I want to know whether I can let the substrings or the prefixs (suffixs) of $x$
be (all of) the sub-instances. Is there a formal definition of sub-instances?
This depends on the context. It could be that you're reading some text where someone has given a formal definition of "sub-instance". If not, then I think it is best to work under the assumption that there is no formal definition of "sub-instance" here.
Given that "sub-instance" is only an informal notion, how do you determine whether something is a sub-instance? The only option is to try it out and see if it works. The idea of something being a sub-instance is equally valid as the idea that it isn't a sub-instance. What you need to do is to determine which of the two ideas is more useful in constructing or reasoning about an algorithm.
Context
StackExchange Computer Science Q#131363, answer score: 4
Revisions (0)
No revisions yet.