|
In computational complexity theory, non-deterministic space or NSPACE is the computational resource describing the memory space for a non-deterministic Turing machine. It is the non-deterministic counterpart of DSPACE. ==Complexity classes== The measure NSPACE is used to define the complexity class whose solutions can be determined by a non-deterministic Turing machine. The complexity class NSPACE(''f''(''n'')) is the set of decision problems that can be solved by a non-deterministic Turing machine, ''M'', using space ''O''(''f''(''n'')), where ''f''(''n'') is the maximum number of tape cells that ''M'' scans on any input of length ''n''. Several important complexity classes can be defined in terms of NSPACE. These include: * REG = DSPACE(''O''(1)) = NSPACE(''O''(1)), where REG is the class of regular languages (nondeterminism does not add power in constant space). * NL = NSPACE(''O''(log ''n'')) * CSL = NSPACE(''O''(''n'')), where CSL is the class of context-sensitive languages. * PSPACE = NPSPACE = * EXPSPACE = NEXPSPACE = The Immerman–Szelepcsényi theorem states that NSPACE(''s''(''n'')) is closed under complement for every function A further generalization is ASPACE, defined with alternating Turing machines. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「NSPACE」の詳細全文を読む スポンサード リンク
|