翻訳と辞書 Words near each other ・ DTE (direct to edit) ・ DTE Energy ・ DTE Energy Electric Company ・ DTE Energy Headquarters ・ DTE Energy Music Theatre ・ DTE80 ・ Dtech it education ・ DTED ・ DTEK ・ DTEK Academy ・ DSP Starter Kit ・ DSP-2230 ・ DSP-4 ・ DSP/BIOS Link ・ DSP1 ・ DSPACE ・ DSpace ・ Dspace ・ DSPACE GmbH ・ DSPAM ・ DSPCA ・ DSPF ・ DSPlayer ・ DSploit ・ DSPnano RTOS ・ DSPS ・ DSQ ・ DSQ Software ・ DSQI ・ DSR Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク DSPACE ： ウィキペディア英語版 DSPACE In computational complexity theory, DSPACE or SPACE is the computational resource describing the resource of memory space for a deterministic Turing machine. It represents the total amount of memory space that a "normal" physical computer would need to solve a given computational problem with a given algorithm. It is one of the most well-studied complexity measures, because it corresponds so closely to an important real-world resource: the amount of physical computer memory needed to run a given program. ==Complexity classes== The measure DSPACE is used to define complexity classes, sets of all of the decision problems which can be solved using a certain amount of memory space. For each function ''f''(''n''), there is a complexity class SPACE(''f''(''n'')), the set of decision problems which can be solved by a deterministic Turing machine using space ''O''(''f''(''n'')). There is no restriction on the amount of computation time which can be used, though there may be restrictions on some other complexity measures (like alternation). Several important complexity classes are defined in terms of DSPACE. These include: * REG = DSPACE(''O''(1)), where REG is the class of regular languages. In fact, REG = DSPACE(''o''(log log ''n'')) (that is, Ω(log log ''n'') space is required to recognize any non-regular language).〔Szepietowski (1994) p.28〕 ''Proof:'' Suppose that there exists a non-regular language ''L'' ∈ DSPACE(''s''(''n'')), for s(n) = ''o''(log log ''n''). Let ''M'' be a Turing machine deciding ''L'' in space ''s''(''n''). By our assumption ''M'' ∉ DSPACE(''O''(1)); thus, for any arbitrary ''k'' ∈ $\backslash mathbb$, there exists an input of ''M'' requiring more space than ''k''. Let ''x'' be an input of smallest size, denoted by n, that requires more space than ''k'', and $\backslash mathcal$ be the set of all configurations of ''M'' on input ''x''. Because ''M'' ∈ DSPACE(''s''(''n'')), then $|\backslash mathcal|\; \backslash le\; 2^$ = ''o''(log ''n''), where ''c'' is a constant depending on ''M''. Let ''S'' denote the set of all possible crossing sequences of ''M'' on ''x''. Note that the length of a crossing sequence of ''M'' on ''x'' is at most $|\backslash mathcal|$: if it is longer than that, then some configuration will repeat, and ''M'' will go into an infinite loop. There are also at most $|\backslash mathcal|$ possibilities for every element of a crossing sequence, so the number of different crossing sequences of ''M'' on ''x'' is According to pigeonhole principle, there exist indexes ''i'' < ''j'' such that $\backslash mathcal\_i(x)=\backslash mathcal\_j(x)$, where $\backslash mathcal\_i(x)$ and $\backslash mathcal\_j(x)$ are the crossing sequences at boundary ''i'' and ''j'', respectively. Let ''x' '' be the string obtained from ''x'' by removing all cells from ''i'' + 1 to ''j''. The machine ''M'' still behaves exactly the same way on input ''x' '' as on input ''x'', so it need the same space to compute ''x' '' as to compute ''x''. However, |''x' ''| < |''x''|, contradicting the definition of ''x''. Hence, there does not exist such language ''L'' as the assumption. □ The above theorem implies the necessity of space-constructible function assumption in the space hierarchy theorem. * L = DSPACE(''O''(log ''n'')) * PSPACE = $\backslash bigcup\_(n^k)$ * EXPSPACE = $\backslash bigcup\_(2^)$ 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「DSPACE」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.