6
$\begingroup$

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?

$\endgroup$
1
  • 4
    $\begingroup$ An interesting, related concept is a matroid. The definition is very general and so a little hard to read, but the idea isn't actually that complicated and if you can prove your problem is a matroid, then you automatically know there is a greedy algorithm which solves it. $\endgroup$
    – kutschkem
    Commented Oct 19, 2020 at 14:10

4 Answers 4

3
$\begingroup$

To add to the other good answers already here consider how subinstances are used in practice. Given an instance (formally a string $x$) we construct another instance (this too we could formally describe as a string $y$). This new string representing our subinstance is the output of some (computable) function of the original instance (We could say $y = f(x)$ for some function $f$). Generally, we assume our original string $x$ has some structure (can be interpreted as a specific type of problem). You could define a language $L' \supseteq L$ that is the set of strings that could be interpreted as the input to the particular type of problem. We know (or at least can check if) $x \in L'$ and then you could say that a "subinstance" should also be in $L'$ (after all, a subinstance should be the same kind of problem). Of course, to make it a "sub"-instance, the new string $y$ should probably be shorter than $x$. Thus, one could define a subinstance of $x \in L'$ to be any string $y \in L'$ such that $|y| < |x|$ and there exists some computable function $f$ such that $f(x) = y$.

However, this definition seems too broad to actually help us do or say anything. But it is kind of fun to think about.

$\endgroup$
1
  • 1
    $\begingroup$ I think this is a good illustration of why we don't formalize this notion in practice. I have one nitpick: if $y$ is a subinstance of $x$ (in the sense that $y$ is used to solve $x$), then $y$ does not necessarily have to be smaller in terms of string length. Suppose we have a DP table $T[x,y,z]$, indexed by 3 variables. Then it is possible that e.g. $T[0,2,2]$ is a subinstance of $T[1,0,0]$, while $(0,2,2)$ is longer than $(1,0,0)$ in a reasonable encoding. So, for your definition to be general enough, you'll probably need a problem specific measure of instance size. $\endgroup$
    – Discrete lizard
    Commented Oct 20, 2020 at 6:51
4
$\begingroup$

I have also not seen a formal definition, and I have seen subinstance and subproblem used interchangeably, but also seem to remember some people separating them (and can find no evidence to support this).

The closest things I have found to a definition on hand:

Subinstances: From the original instance, construct one or more subinstances, which are smaller instances of the same problem. - How to Think About Algorithms, J. Edmonds, p.165

Jeff Erikson's "Algorithms", Kleinberg & Tardos' "Algorithm Design" and Steven Skiena's "The Algorithm Design Manual" don't have convenient definitions or quotes, but all use the term "subproblem" to mean the same as Edmond's use of "subinstance", all apparently with the expectation that reader will either already understand or understand implicitly.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

Not that I know of. But see here for some common patterns in dynamic programming algorithms: What is dynamic programming about?.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.