Find the word definition



SC, Sc or sc may refer to:

SC (complexity)

In computational complexity theory, SC (Steve's Class, named after Stephen Cook) is the complexity class of problems solvable by a deterministic Turing machine in polynomial time (class P) and polylogarithmic space (class PolyL) (that is, O((log n)) space for some constant k). It may also be called DTISP(poly, polylog), where DTISP stands for deterministic time and space. Note that the definition of SC differs from PPolyL, since for the former, it is required that the algorithm runs in both polynomial time and polylogarithmic space; while for the latter, two separate algorithms will suffice: one that runs in polynomial time, and another which runs in polylogarithmic space. (It is unknown whether SC and PPolyL are equivalent).

DCFL, the strict subset of context-free languages recognized by deterministic pushdown automata, is contained in SC, as shown by Cook in 1979.

It is open if directed st-connectivity is in SC, although it is known to be in PPolyL (because of a DFS algorithm and Savitch's theorem). This question is equivalent to NLSC.

RL and BPL are classes of problems acceptable by probabilistic Turing machines in logarithmic space and polynomial time. Noam Nisan showed in 1992 the weak derandomization result that both are contained in SC. In other words, given polylogarithmic space, a deterministic machine can simulate logarithmic space probabilistic algorithms.



n. (abbreviation of softcover English)

Usage examples of "sc".

SCS is headquartered in a heavily protected compound of modern buildings on Springfield Road in Beltsville, Maryland, a few miles south of NSA.

His instincts told him that, repeatedly, and they were proven correct when a flashing scim itar intercepted the dart.