A következőkben bevezetjük a feladat megadásának egy másik módját, és kimondunk egy a gyakorlat szempontjából nagyon fontos tételt.

Általában a feladat nem függ az állapottér összes komponensétől, azaz az állapottér több pontjához is ugyanazt rendeli. Ezeket a pontokat fogjuk össze egy ponttá a paramétertér segítségével.

Fontos észrevenni, hogy paraméterteret mindig lehet találni. Például maga a feladat állapottere minden esetben választható paramétertérnek úgy, hogy a definícióban szereplő relációnak az identikus leképezést, -nek pedig magát az feladatot választjuk. Ám az, hogy egy konkrét esetben mit is választunk paramétertérnek a feladattól függ. Általában úgy választjuk meg a paraméterteret, hogy a következő tételt kényelmesen tudjuk használni.

3.2. TéTEL: SPECIfiKáCIó TéTELE Legyen feladat, az egy paramétertere, , , Legyen , és definiáljuk a következő állításokat:

Ekkor ha akkor az program megoldja az feladatot.

Bizonyítás: A megoldás definíciója két pontjának teljesülését kell belátnunk:

_

A specifikáció tétele csak elégséges feltétel a megoldásra, azaz nem megfordítható: lehet adni olyan feladat-program párt, ahol a program megoldja a feladatot, de a specifikáció tétele nem teljesül. Ez természetesen attól is függ, hogy a feladatot hogyan specifikáljuk, azaz milyen paraméterteret választunk, és hogyan bontjuk a feladatot és relációk kompozíciójára.

Azonnal látszik, hogy

Ha egy -re , akkor .