Komplement (kompleksitet) - Complement (complexity)
I beregningskompleksitetsteori er komplementet af et beslutningsproblem det beslutningsproblem, der skyldes at vende ja og nej svarene. Tilsvarende, hvis vi definerer beslutningsproblemer som sæt af begrænsede strenge, så er komplementet af dette sæt over et fast domæne dets komplementproblem.
For eksempel er et vigtigt problem, om et tal er et primtal . Dens komplement er at bestemme, om et tal er et sammensat tal (et tal, der ikke er primtal). Her er komplementets domæne mængden af alle heltal, der overstiger et.
Der er en Turing -reduktion fra hvert problem til dets komplementproblem. Komplementoperationen er en involution , hvilket betyder at den "fortryder sig selv", eller komplementets komplement er det oprindelige problem.
Man kan generalisere dette til komplementet til en kompleksitetsklasse , kaldet komplementklassen , som er et sæt komplementer til ethvert problem i klassen. Hvis en klasse kaldes C , er dens komplement konventionelt mærket co-C . Bemærk, at dette ikke er komplementet til kompleksitetsklassen i sig selv som et sæt problemer, som ville indeholde langt flere problemer.
En klasse siges at være lukket under komplement, hvis komplementet til ethvert problem i klassen stadig er i klassen. Fordi der er Turing -reduktioner fra hvert problem til dets komplement, lukkes enhver klasse, der er lukket under Turing -reduktioner, under komplement. Enhver klasse, der lukkes under komplement, er lig med dens komplementklasse. Under mange-en-reduktioner menes mange vigtige klasser, især NP , at adskille sig fra deres komplementklasser (selvom dette ikke er bevist).
Den lukning af enhver kompleksitet klasse under Turing reduktioner er en overordnet denne klasse, som er lukket under komplement. Lukningen under komplement er den mindste sådan klasse. Hvis en klasse skæres med sit komplement, får vi et (muligvis tomt) undersæt, der lukkes under komplement.
Hver deterministisk kompleksitetsklasse ( DSPACE (f (n)), DTIME (f (n)) for alle f (n)) lukkes under komplement, fordi man simpelthen kan tilføje et sidste trin til algoritmen, der vender svaret. Dette virker ikke for ikke -deterministiske kompleksitetsklasser, for hvis der findes både beregningsveje, der accepterer og stier, der afviser, og alle stier vender deres svar, vil der stadig være stier, der accepterer og stier, der afviser - følgelig accepterer maskinen i begge sager.
Nogle af de mest overraskende kompleksitetsresultater, der er vist til dato, viste, at kompleksitetsklasserne NL og SL faktisk er lukket under komplement, hvorimod det før var udbredt tro, at de ikke var det (se Immerman – Szelepcsényi sætning ). Sidstnævnte er blevet mindre overraskende, nu hvor vi kender SL lig med L , hvilket er en deterministisk klasse.
Hver klasse, der er lav for sig selv, lukkes under komplement.
