<テクニカルレポート>
Parallel Complexity and P-Complete Problems

作成者
本文言語
出版者
発行日
雑誌名
出版タイプ
アクセス権
概要 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.続きを見る

本文情報を非表示

rifis-tr-6 pdf 1.9 MB 116  

詳細

レコードID
査読有無
関連情報
注記
タイプ
登録日 2009.04.22
更新日 2017.01.20