Complement (complexitate)
În teoria complexității de calcul , complementul unei probleme de decizie este problema rezultată din inversarea răspunsurilor da și nu . [1] În mod echivalent, dacă definim o problemă de decizie ca un set de șiruri finite, atunci complementul acestui set pe un anumit domeniu este problema sa complementară. [2]
De exemplu, o problemă importantă este dacă un număr este sau nu prim . Complementul său este de a determina dacă un număr este compus (adică dacă nu este prim). În acest caz, domeniul complementului este ansamblul tuturor numerelor întregi, cu excepția unuia. [3]
Există o reducere Turing de la fiecare problemă la complementul ei. [4] Operația complementară este involuția , adică complementul complementului problemei inițiale.
Noțiunile anterioare pot fi extinse la nivelul claselor de complexitate , obținându-se astfel conceptul de clasă complement (sau clasă complementară ), care este setul de complemente ale tuturor problemelor clasei date. [5] Luând orice clasă C , complementul său este indicat în mod convențional cu co-C . Rețineți că o clasă complement nu este complementul clasei ca set de probleme, care ar conține un număr mult mai mare de probleme.
Se spune că o clasă de complexitate este închisă în raport cu complementul dacă complementul fiecărei probleme a clasei aparține clasei în sine. [6] Întrucât există o reducere Turing de la fiecare problemă la complementul său, orice clasă care este închisă față de reducerile Turing este închisă față de complement. Fiecare clasă închisă față de complement este egală cu clasa sa complementară. În ceea ce privește clasele închise în ceea ce privește așa-numitele reduceri „multe-unu”, totuși, se crede că multe clase importante (inclusiv NP , în special) sunt distincte de complementul lor (în mod specific, co-NP ), chiar dacă nu a fost încercat. [7]
Fiecare clasă de complexitate deterministă (DSPACE ( f (n) ), DTIME ( f (n) ), pentru fiecare f (n) ) este închisă în raport cu complementul, [8] deoarece putem adăuga pur și simplu un ultim pas la algoritm care inversează răspunsul. Acest expedient nu funcționează pentru clase de complexitate nedeterministe: date, de fapt, două căi de calcul, una acceptând și una respingând, în timp ce ne asigurăm că își anulează rezultatul, vor continua să existe două căi, dintre care una va fi acceptarea; prin urmare, mașina, într-un mod nedeterminist, va găsi în continuare calea de a accepta și problema va continua să aibă un rezultat pozitiv (și, în consecință, nu va reprezenta complementul problemei de pornire).
Notă
- ^ (EN) Kiyosi Itô, Dicționar enciclopedic de matematică, volumul 1 , MIT Press, 1993, p. 269, ISBN 9780262590204 .
- ^ (EN) Alexander Schrijver, Theory of Linear and Integer Programming , Wiley Series in Discrete Mathematics & Optimization, John Wiley & Sons, 1998, p. 19, ISBN 9780471982326 .
- ^ (EN) Steven Homer și Alan L. Selman, Computability and Complexity Theory, Texts in Computer Science, Springer, 2011, ISBN 9781461406815 .
- ^ (EN) Arindama Singh, Elements of Computation Theory , Texts in Computer Science, Springer, 2009, p. 287 (exercițiul 9.10), ISBN 9781848824973 .
- ^ (EN) Daniel Bovet și Pierluigi Crescenzi, Introducere în teoria complexității , Prentice Hall International Series in Computer Science, Prentice Hall, 1994, pp. 133 –134 , ISBN 9780139153808 .
- ^ (EN) Heribert Vollmer, Introducere în complexitatea circuitelor: o abordare uniformă , texte în informatică teoretică. O serie EATCS, Springer, 1999, p. 113, ISBN 9783540643104 .
- ^ (EN) R. Pruim și Ingo Wegener, Teoria complexității: explorarea limitelor algoritmilor eficienți , Springer, 2005, p. 66, ISBN 9783540274773 .
- ^ (EN) Giorgio Ausiello, Complexitate și aproximare: probleme de optimizare combinatorie și proprietățile lor de aproximabilitate , Springer, 1999, p. 189, ISBN 9783540654315 .
