4
$\begingroup$

It is a very standard situation that we have a class of problems $P$, and a subclass $\tilde P\subset P$ which has a certain restricted property.

For example, $P$ could be the problem of searching through an arbitrary list of people for someone with height $1.8$ meters, while $\tilde P$ could be the same problem, except that it is known that the list is ordered by height.

Searching through an ordered list is far more efficient than through an arbitrary list.

My question is: what would be the term for an algorithm using/relying on a certain particular structure of the problem in order to run more efficiently than would be needed in the general case?

Or alternatively, what is the term for "omitting calculations" that are necessary to do in the general case but that can be omitted in the restricted problem case?

Improve this question
$\endgroup$

5 Answers 5

Reset to default
2
$\begingroup$

I'd call it "special-casing".

There are variations. Variation 1 would be: You examine the input, and if the input has a special form, then you use an algorithm that cannot handle every input, but only input like the one you detected.

Variation 2: You run an algorithm that will run fast, but will not be successful for every possible input. You may detect while you run the algorithm or after you ran it that it failed, and use a more general algorithm.

Variation 3: You run a general algorithm, knowing that it will be fast in some cases, and hope your case is a fast one.

Improve this answer
$\endgroup$
1
  • $\begingroup$ +1 for first point (and fact that this is proper answer unlike promise or reduction) but variant 2 is not using inherent property and vatiant 3 uses luck as optimisation, with these I do not agree. $\endgroup$
    – Evil
    Jan 22, 2019 at 2:03
1
$\begingroup$

The common name is just optimisation which in this context may be elaborated as restricted case or like gnasher729 mentioned: special case.

The concept of cutting needless calculations is called lazy evaluation or call-by-need. When you have to handle general case, all computations are required, but if you hit deegenerate case, some calculations are simply ommited.

Another term is specialization, when function takes inherent structure of the problem, and is suited only to given case (but unlike lazy evaluation or special casing, it never checks if input is restricted, it is assumed from the start).

Improve this answer
$\endgroup$
0
$\begingroup$

The concept you are looking for is very close to that of promise problems. Although promise problems are usually related to decision problems, you could easily generalize the concept to search problems.

The algorithm solving a promise problem is allowed to have an unspecified behavior on instances which do not fulfil the promise. Hence, you could set the promise to be the property you are relying on and then analyze the complexity of algorithms which must work correctly only for inputs that satisfy the promise.

(Adding an alternative answer in response to criticism to my other answer. This seems to better address the penultimate question in the OP (i.e, relying on properties of the input), while the other one (i.e., "reductions") better suits "omitting calculations", that is, the last question in the OP.)

Improve this answer
$\endgroup$
0
$\begingroup$

From what I've seen, there isn't a single technical term for this but people tend to use phrases involving the word "restricting" or "restriction", such as "restricting the input", "restricting to the case where..." and so on.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Would the downvoter care to explain. This is a term that is actually used. $\endgroup$
    – David Richerby
    Jan 21, 2019 at 13:10
  • 1
    $\begingroup$ Not the downvoter, but answers are often assumed to have a certain degree of certainty/"self confidence" to them, "I don't know anything more specific" sounds a bit too much on the uncertain side. You might be able to improve this answer by showing have the term "restricting the input" is used within this context. $\endgroup$
    – Discrete lizard ♦
    Jan 21, 2019 at 17:51
  • $\begingroup$ Not downvoter, I do not do that (+1 actually), but I think that restricted case optimisation is more accurate description here. I would suggest to rewrite first part into no consensus about term, since several answers were given, and in fact every subfield uses slightly different terminology ;) $\endgroup$
    – Evil
    Jan 22, 2019 at 2:07
-1
$\begingroup$

The term you are looking for is reduction, which is a central aspect of complexity theory. In particular, what you want are so called efficient (or poly-time) Turing reductions (also called Cook reductions).

We say a problem $A$ is Turing reducible to a problem $B$ if there is a TM which solves $A$ if provided with an oracle for $B$. (An oracle is a device which answers a query in $B$ with runtime cost 1.) The reduction is efficient if the TM can perform it in polynomial time in the length of its input.

Note the above applies not only to decision but also to search problems (as you are probably more interested in the latter.)

For specific problems, you may want to set a stricter asymptotic bound (than simply polynomial) on the reduction depending on the asymptotic lower bound of problem $B$. For example, a reduction of a problem $A$ to sorting should take not only polynomial but actually $o(n \log n)$ time; otherwise, the reduction is meaningless since it is powerful enough to solve $B$ (i.e., sorting) directly.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ I'm not convinced that this is correct. A reduction takes a general class of problem instances $P$, and converts every one of them into a different problem $Q$. I am talking about the situation where we have a subset of problem instances of $P$, which have a property that allow a more efficient algorithm to be used to solve them. $\endgroup$
    – user626625
    Dec 22, 2018 at 8:32
  • $\begingroup$ @user626625 The definition does not require $Q$ to be disjoint or different from $P$. $Q$ may also be a subset of $P$ or, even, $P$ itself. $\endgroup$
    – dkaeae
    Dec 22, 2018 at 9:25
  • 1
    $\begingroup$ but terminologically, "reduction" doesn't capture the thing I'm describing $\endgroup$
    – user626625
    Dec 22, 2018 at 10:49
  • $\begingroup$ @user626625 I am not sure what you mean by "terminologically". I insist the reduction concept captures perfectly what you want: You reduce $P$ to $\tilde{P}$; the "omitted calculations" are, precisely, the reduction which is performed. As in the question, you can then argue the restricted case $\tilde{P}$ can be solved efficiently while it is the reduction part (i.e., transforming the instance so it satisfies a particular structure or property) that is expensive. $\endgroup$
    – dkaeae
    Dec 22, 2018 at 11:46
  • 1
    $\begingroup$ @dkaeae It's not reduction at all. Reduction says "I can solve any A by solving a B instead." The situation here is that algorithms that can solve every A are slow, but we're only interested in inputs with some special property and assuming that property allows a faster algorithm. $\endgroup$
    – David Richerby
    Jan 21, 2019 at 11:28

Your Answer

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

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