文献

J-GLOBAL ID：201502230652202475   整理番号：15A0487431

時間無依存組織Pシステムのパワー:NP完全問題への取り組み

The power of time-free tissue P systems: Attacking NP-complete problems

著者 (6件)： LIU Xiangrong (Dep. of Computer Sci. in Xiamen Univ., Xiamen 361005, CHN) ,  LIU Xiangrong (Dep. of Electric and Computer Engineering, Micro and Nanotechnology Lab, Univ. of Illinois at Urbana-Champaign, IL, USA) ,  SUO Juan (Dep. of Computer Sci. in Xiamen Univ., Xiamen 361005, CHN) ,  LEUNG Stephen C.H. (Dep. of Management Sciences, City Univ. of Hong Kong, Hong Kong) ,  LIU Juan (Dep. of Mechanical and Electrical Engineering, Inst. of Physical and Mechanical and Electrical Engineering in Xiamen ...) ,  ZENG Xiangxiang (Dep. of Computer Sci. in Xiamen Univ., Xiamen 361005, CHN)
資料名： Neurocomputing  (Neurocomputing)
巻： 159  ページ： 151-156  発行年： 2015年07月02日 
JST資料番号： W0360A  ISSN： 0925-2312  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 生物学的構造と機能から触発された組織Pシステムは,分散型並列計算機モデルの1つである。従来の組織Pシステムでは,(生化学反応から抽象化された)各ルールは,正確でグローバルな実行時間を有している。実行時間の制約は,生化学反応の実行時間が外部の制御不能な条件で変動する為に,生物学的事実とは一致しない。本論文は,時間無依存組織Pシステムと名付けた,各ルールの実行時間制限が無い組織Pシステムの1つを研究した。その結果,ルールの実行時間は,システムの計算時間に影響しないことが分かった。また,時間無依存組織Pシステムの計算効率を考慮し,最大クリーク問題とハミルトン路問題が,課題のサイズに関して多項式時間で解決出来ることを証明した。Copyright 2015 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.

シソーラス用語： *NP完全問題 ,  *並列計算機 ,  抽象 ,  変化 ,  時間 ,  最大化問題 ,  Hamilton路
準シソーラス用語： 最大クリーク問題 ,  実行時間 ,  生化学変化 ,  抽象化 ,  *同一並列計算機

分類 (2件)： 人工知能  (JE08000Z) ,  計算理論  (JB02000A)

タイトルに関連する用語 (3件)： 組織 ,  パワー ,  NP完全問題