SC (Komplexität)

Im Computerkomplexitätstheorie, SC (Steves Klasse, benannt nach Stephen Cook)[1] ist der Komplexitätsklasse von Problemen lösbar durch a deterministische Turing -Maschine in der Polynomzeit (Klasse P) und Polylogarithmischer Raum (Klasse PolyL) (das ist, O((Protokoll n)k) Raum für einige Konstante k). Es kann auch genannt werden DTISP (Poly, Polylog), wo Dtisp steht für deterministische Zeit und Raum. Beachten Sie, dass die Definition von SC unterscheidet sich von P ∩ PolyLDa für erstere, muss ein einzelner Algorithmus sowohl im Polynomzeit als auch im Polylogarithmischen Raum ausgeführt werden; Während für letztere werden zwei getrennte Algorithmen ausreichen: eine, die in der Polynomzeit läuft, und ein anderer, der im Polylogarithmischen Raum läuft. (Es ist nicht bekannt, ob SC und P ∩ PolyL sind gleichwertig).

DCFLdie strenge Teilmenge von Kontextfreie Sprachen erkannt von Deterministische Pushdown -Automaten, ist in enthalten in SC, wie von Cook im Jahr 1979 gezeigt.[2] Ist es offen, wenn alle kontextfreien Sprachen in anerkannt werden können in SC, obwohl sie bekannt sind in P ∩ PolyL.[3]

Es ist offen, wenn es gerichtet ist ST-Verbindlichkeit ist in SC, obwohl es bekannt ist, in zu sein P ∩ PolyL (Wegen eines DFS -Algorithmus und Savitchs Theorem). Diese Frage entspricht zu Nl ⊆ SC.

Rl und Bpl sind Klassen von Problemen, die von akzeptabel sind durch Probabilistische Turing -Maschinen im logarithmischen Raum und Polynomzeit. Noam Nisan zeigten 1992 die Schwachen Derandomisierung Ergebnis, dass beide in enthalten sind in SC.[4] Mit anderen Worten, gegeben Polylogarithmic Raum, eine deterministische Maschine kann simulieren logarithmisch Raumprobabilistische Algorithmen.

Verweise

  1. ^ Komplexitätszoo: SC
  2. ^ S. A. Cook. Deterministische CFLs werden gleichzeitig in der Polynomzeit und im quadratischen logarithmischen Raum akzeptiert. Verfahren von ACM STOC'79, S. 338–345. 1979.
  3. ^ TCS Stack Exchange: CFG -Parsen mit O (n^2) Raum
  4. ^ Nisan, Noam (1992), "Rl ⊆ Sc", Verfahren des 24. ACM -Symposiums über die Computertheorie (STOC '92), Victoria, British Columbia, Kanada, S. 619–623, doi:10.1145/129712.129772.