e/Immerman-Szelepcsenyi theorem

Information
has gloss	eng: In the field of computational complexity, the Immerman–Szelepcsényi theorem was proven independently by Neil Immerman and Róbert Szelepcsényi in 1987, for which they shared the 1995 Gödel Prize. In its general form the theorem states that NSPACE(s(n)) = co-NSPACE(s(n)) for all reasonable functions s(n). In other words, if a nondeterministic machine can solve a problem, it can solve its complement problem (with the yes and no answers reversed) in the same asymptotic amount of space. No similar result is known for the time complexity classes.
lexicalization	eng: Immerman-Szelepcsenyi Theorem
lexicalization	eng: Immerman-Szelepcsényi theorem
lexicalization	eng: Immerman–Szelepcsényi theorem
instance of	e/Complexity class

Meaning
German
has gloss	deu: Der Satz von Immerman und Szelepcsényi ist ein Satz aus der Komplexitätstheorie und besagt, dass die Klasse NSPACE unter dem Komplement abgeschlossen ist.
lexicalization	deu: Satz von Immerman und Szelepcsényi
Hebrew
has gloss	heb: משפט אימרמן (Immerman–Szelepcsényi) הוא תוצאה בתורת הסיבוכיות (ענף במדעי המחשב) המראה כי מחלקות סיבוכיות מקום אי דטרמיניסטיות סגורות לפעולת המשלים (בעוד אותה שאלה עבור סיבוכיות זמן עודנה פתוחה וייתכן כי התשובה לה שלילית). המשפט הוכח בשנת 1987 באופן בלתי תלוי בידי ניל אימרמן ו-Róbert Szelepcsényi, אשר זכו ב-1995 בפרס גדל על תוצאה זו.
lexicalization	heb: משפט אימרמן