| 翻訳と辞書 |
NL-complete
In computational complexity theory, NL-complete is a complexity class containing the languages that are complete for NL, the class of decision problems that can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space. The NL-complete languages are the most "difficult" or "expressive" problems in NL. If a method exists for solving any one of the NL-complete problems in logarithmic memory space, then NL = L.
==Definitions==
NL consists of the decision problems that can be solved by a nondeterministic Turing machine with a read-only input tape and a separate read-write tape whose size is limited to be proportional to the logarithm of the input length. Similarly, L consists of the languages that can be solved by a deterministic Turing machine with the same assumptions about tape length. Because there are only a polynomial number of distinct configurations of these machines, both L and NL are subsets of the class P of deterministic polynomial-time decision problems.
Formally, a decision problem is NL-complete when it belongs to NL, and has the additional property that every other decision problem in NL can be reduced to it. Unless otherwise specified, the reductions in this definition are assumed to be many-one reductions by a deterministic logarithmic-space algorithm.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「NL-complete」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|