翻訳と辞書
Words near each other
・ P-benzoquinone reductase (NADPH)
・ P-bodies
・ P-Bone Steak
・ P-box
・ P-CAD
・ P-chart
・ P-Chlorocresol
・ P-class cruiser
・ P-class sloop
・ P-class submarine
・ P-class yacht
・ P-code
・ P-code machine
・ P-Com
・ P-compact group
P-complete
・ P-constrained group
・ P-Coumaric acid
・ P-Coumaric acid glucoside
・ P-Coumaroylated anthocyanin
・ P-Course
・ P-Cresol
・ P-Cube
・ P-cycle protection
・ P-Cymene
・ P-Delta Effect
・ P-derivation
・ P-Dimethylaminocinnamaldehyde
・ P-factor
・ P-FEM


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

P-complete : ウィキペディア英語版
P-complete
In complexity theory, the notion of P-complete decision problems is useful in the analysis of both:
# which problems are difficult to parallelize effectively, and;
# which problems are difficult to solve in limited space.
Formally, a decision problem is P-complete (complete for the complexity class P) if it is in P and every problem in P can be reduced to it by using an appropriate reduction.
The specific type of reduction used varies and may affect the exact set of problems. If we use NC reductions, that is, reductions which can operate in polylogarithmic time on a parallel computer with a polynomial number of processors, then all P-complete problems lie outside NC and so cannot be effectively parallelized, under the unproven assumption that NC ≠ P. If we use the weaker log-space reduction, this remains true, but additionally we learn that all P-complete problems lie outside L under the weaker unproven assumption that L ≠ P. In this latter case the set P-complete may be smaller.
== Motivation ==

The class P, typically taken to consist of all the "tractable" problems for a sequential computer, contains the class NC, which consists of those problems which can be efficiently solved on a parallel computer. This is because parallel computers can be simulated on a sequential machine.
It is not known whether NC = P. In other words, it is not known whether there are any tractable problems that are inherently sequential. Just as it is widely suspected that P does not equal NP, so it is widely suspected that NC does not equal P.
Similarly, the class L contains all problems that can be solved by a sequential computer in logarithmic space. Such machines run in polynomial time because they can have a polynomial number of configurations. It is suspected that L ≠ P; that is, that some problems that can be solved in polynomial time also require more than logarithmic space.
Similarly to the use of NP-complete problems to analyze the P = NP question, the P-complete problems, viewed as the "probably not parallelizable" or "probably inherently sequential" problems, serves in a similar manner to study the NC = P question. Finding an efficient way to parallelize the solution to some P-complete problem would show that NC = P. It can also be thought of as the "problems requiring superlogarithmic space"; a log-space solution to a P-complete problem (using the definition based on log-space reductions) would imply L = P.
The logic behind this is analogous to the logic that a polynomial-time solution to an NP-complete problem would prove P = NP: if we have a NC reduction from any problem in P to a problem A, and an NC solution for A, then NC = P. Similarly, if we have a log-space reduction from any problem in P to a problem A, and a log-space solution for A, then L = P.

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「P-complete」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.