Hvorfor står «delinstans» oppført i ordlista som oversettelse av «subproblem»?

Kortversjon: Det er helt greit å bruke «delproblem».

En direkte oversettelse av lærebokas terminologi gir her «delproblem», og det er et begrep som er mye brukt, og også helt akseptabelt i dette emnet. Likevel er det mer presist å snakke om delinstanser, og mange forfattere bruker også «subinstance» på engelsk.

Ta for eksempel lærebokas beskrivelse av splitt-og-hersk-algoritmer:

Divide the problem into a number of subproblems that are smaller instances of the same problem.

Her brukes ordet «problem» på to ulike måter. På slutten av setningen er det snakk om et problem i ordinær forstand, f.eks. sortering, og vi snakker om instanser av dette problemet. Men i starten av setningen er det snakk om en instans, som her uformelt omtales som «the problem».

Det ser vi klart av eksemplet som gis rett nedenfor:

Divide the $n$-element sequence to be sorted into two subsequences of $n/2$ elements each.

Her er det klart at «the problem», i form av en spesifikk sekvens av lengde $n$, er en instans av det generelle problemet, altså sortering.

Vi kan også oversette «subproblem graph» til «delinstansgraf» heller enn  «delproblemgraf».

Når vi snakker om det generelle problemet blir det litt annerledes. Vi sier gjerne (litt uformelt) at et problem har overlappende delproblemer. Det betyr at det finnes instanser av problemet med overlappende delinstanser.