| 作成者 |
|
| 本文言語 |
|
| 出版者 |
|
|
|
| 発行日 |
|
| 収録物名 |
|
| 巻 |
|
| 出版タイプ |
|
| アクセス権 |
|
| 関連DOI |
|
|
|
| 関連URI |
|
|
|
| 関連情報 |
|
|
|
| 概要 |
The class NC consists of probiem solvable by parallel algorithms running in time $ Oleft((log n)^k/right) $ using polynomial number of processors for some $ k gep 0 $. It is strongly believed that $ ...P \eq NC $ . If $ P \eq NC $ is assumed, the P-completeness of a problem implies that no eficient parallel algorithm exists for the problem. This paper presents very general P-comp!eteness theorems which yield a new series of P-complete problems including the lexicographically first maximal independent set problem (Cook 1983). We also give a rnethod of firding parallelisrn in some kind of sequential algorithms.続きを見る
|
Mendeley出力
rifis-tr-6