翻訳と辞書 Words near each other ・ PSORTdb ・ Psorula ・ Psorya ・ PSOS ・ PSOS (real-time operating system) ・ Psota ・ Psote ・ Psotnik ・ Psou (village) ・ Psou River ・ Psoy Korolenko ・ PSP (disambiguation) ・ PSP Media Manager ・ PSP Padang ・ PSPACE ・ PSPACE-complete ・ PSPad ・ PSPCasting ・ Pspell ・ PSPH ・ PSPI ・ PSpice circuit file ・ PSPJ Pidie Jaya ・ PSPLab ・ PSPP ・ PSPP Padang Panjang ・ PSPS Pekanbaru ・ PSPS U-21 ・ Pspyched! ・ PSQL Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク PSPACE-complete ： ウィキペディア英語版 PSPACE-complete In computational complexity theory, a decision problem is PSPACE-complete if it can be solved using an amount of memory that is polynomial in the input length (polynomial space) and if every other problem that can be solved in polynomial space can be transformed to it in polynomial time. The problems that are PSPACE-complete can be thought of as the hardest problems in PSPACE, because a solution to any one such problem could easily be used to solve any other problem in PSPACE. The PSPACE-complete problems are widely suspected to be outside the more famous complexity classes P and NP, but that is not known. It is known that they lie outside of the class NC (a class of problems with highly efficient parallel algorithms), because problems in NC can be solved in an amount of space polynomial in the logarithm of the input size, and the class of problems solvable in such a small amount of space is strictly contained in PSPACE by the space hierarchy theorem. ==Examples== Below are descriptions of a few PSPACE-complete problems. More examples can be found at the list of PSPACE-complete problems. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「PSPACE-complete」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.