konjunkt sorrendezés

Kapcsolódó fogalmak: 
elsőrendű logika
Kapcsolódó fogalmak: 
konjunkció
Kapcsolódó fogalmak: 
kényszerkielégítési probléma (CSP)
Rövid szöveges bemutatás: 
A konjunkt sorrendezés egy optimalizációs probléma, mely önmagában NP nehéz, azaz nem ismert rá polinomiális végrehajtási idejű algoritmus. A feladat az elsőrendű logikához kapcsolódik. Az elsőrendű logikában fel tudunk írni szabályokat, olyan szabályokat melyek állnak egy előfeltétel részből és egy következtetésből, ami akkor valósul meg hogyha az előfeltételek igazak, tehát a -> b, ha-akkor típusú szabályok. Az előfeltételek sorrendezése a feladat, úgy, hogy ha az előfeltétel nem fog teljesülni az minél kevesebb költséggel, azaz minél gyorsabban kiderüljön. Tehát a feladat az előfeltételek olyan vizsgálati sorrendjének megállapítása, hogy minél előbb lehessen megbizonyosodni arról, hogy az előfeltételek közül valami nem teljesül. Erre különböző algoritmusokat implementáltak, de egyik se jelentett igazi áttörést.