Problema admisibilităţii

O problemă de admisibilitate X este o pereche (D, F), cu , īn care D este o mulţime de instanţe ale lui X şi este formată din şiruri binare finite, iar F reprezintă instanţele admisibile. Dānd o instanţă particulară , dorim să determinăm cānd şi acest lucru se face printr-un răspuns afirmativ sau negativ.

EXEMPLE:

1. Admisibilitatea pentru (0-1 IP)

D este mulţimea tuturor matricilor īntregi (A, b). O instanţă este specificată prin valorile īntregi m şi n de dimensionare a matricii A şi de valorile numerice pentru elementele matricii A şi a vectorului b şi

.

2. Mărginirea inferioară pentru (0-1 IP)

D={(A, b, c, z)}, unde toate elementele sunt īntregi şi

.

Această problemă este strāns legată de problema de optimizare prin faptul că, dacă şi , atunci .

urmator