文献

J-GLOBAL ID：201602011174549329   整理番号：70A0261088

計算の複雑さにおける決定不能性の考察

Decision problems for complexity classes of computable functions.

著者 (1件)： LEWIS F D
資料名： Proc Annu ACM Symp Theory  (Proceedings of the Annual ACM Symposium on Theory of Computing)
巻： 2  ページ： 22-30  発行年： 1970年 
JST資料番号： D0804A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 帰納的関数の計算の複雑さの研究において,最近リソース(resourcの制限の測定に対する一般的公理の集合が導入された。しかし・この一般的公理は測定に望ましくない特性を許すことになり,そのため望ましい測度を定義するように公理を制限しようとする多くの試みがなされている。ここでは,複雑さのクラスやそのクラスに関するいくつかの集合の決定不能性を調べる。これらの集合を決定不能性のdeggeeによって分類し,これらのdegreeが同一になるように測度に制限を置く。これは測度の自然さに対し新たな基準を与えるもの,と思われる;写図10参19

シソーラス用語： 計算の複雑さ ,  決定問題
準シソーラス用語： 計算の理論

タイトルに関連する用語 (2件)： 計算の複雑さ ,  決定不能性