講演抄録/キーワード |
講演名 |
2011-10-21 14:25
解析学における高階計算量 ○河村彰星(東大)・スチーブン クック(トロント大) COMP2011-32 |
抄録 |
(和) |
実数,実数集合,実函数など近似によってのみ表される対象を入出力とする問題について計算量を論ずるための枠組の拡張を提案する.これらの対象を符号化する名として従来しばしば用いられた無限文字列に代えて文字列から文字列への函数(の一部)を用いることにより,より多くの場合に計算量を扱うことができる.これは高階計算量の分野に倣って文字列函数に長さを定めることで,これを入力とする計算に費やす時間ないし空間が「多項式で抑えられる」ことを定義できることによる.これにより計算量級P,NP,PSPACE並びに適切な帰着の下でのNP完全,PSPACE完全の概念が,より一般の対象に拡張せられる.
この枠組では機械による計算とその意味とが截然と分れているため,新たな対象へ応用するには符号化法を指定するだけでよい.本稿では実数,実数集合,実函数を入出力とする計算を考える.このうち実数集合と実函数は従来の無限文字列による方法では適切な符号化ができなかったため,これらを入出力とする演算の計算量を扱うのは本稿の方法が初である.例えば微分方程式を数値的に解くという課題は,実函数を実函数へ移す演算子とみるのが自然であるが,そのような演算子の計算量を述べる枠組が無かったために既存の結果では演算子の値である実函数の計算量が如何に高くなり得るかを述べるに留まっていた.本稿の方法によりこれを改良して演算子そのものが多項式空間完全であることを示すことができる. |
(英) |
We propose a new framework for discussing the computational complexity of problems involving uncountably many objects, such as real numbers, sets and functions, that can be represented only through approximation. The key idea is to use (a certain class of) string functions as names representing these objects. These are more expressive than infinite sequences, which served as names in prior work that formulated complexity in more restricted settings. An important advantage of using string functions is that we can define their "size" in the way inspired by higher-type complexity theory. This enables us to talk about computation on string functions whose time or space is bounded polynomially in the input size, giving rise to more general analogues of the classes P, NP, and PSPACE. We also define NP- and PSPACE-completeness under suitable many-one reductions.
Because our framework separates machine computation and semantics, it can be applied to problems on sets of interest in analysis once we specify a suitable representation (encoding). As prototype applications, we consider the complexity of functions (operators) on real numbers, real sets, and real functions. The latter two cannot be represented succinctly using existing approaches based on infinite sequences, so ours is the first treatment of functions on them. As an interesting example, the task of numerical algorithms for solving the initial value problem of differential equations is naturally viewed as an operator taking real functions to real functions. As there was no complexity theory for operators, previous results could only state how complex the solution can be. We now reformulate them and show that the operator itself is polynomial-space complete. |
キーワード |
(和) |
計算可能解析 / 計算量 / 二階多項式 / 表現 / / / / |
(英) |
computable analysis / computational complexity / representations / second-order polynomials / / / / |
文献情報 |
信学技報, vol. 111, no. 256, COMP2011-32, pp. 25-32, 2011年10月. |
資料番号 |
COMP2011-32 |
発行日 |
2011-10-14 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2011-32 |
研究会情報 |
研究会 |
COMP |
開催期間 |
2011-10-21 - 2011-10-21 |
開催地(和) |
東北大学 |
開催地(英) |
Tohoku Univ. |
テーマ(和) |
|
テーマ(英) |
|
講演論文情報の詳細 |
申込み研究会 |
COMP |
会議コード |
2011-10-COMP |
本文の言語 |
日本語 |
タイトル(和) |
解析学における高階計算量 |
サブタイトル(和) |
|
タイトル(英) |
Complexity Theory for Operators in Analysis |
サブタイトル(英) |
|
キーワード(1)(和/英) |
計算可能解析 / computable analysis |
キーワード(2)(和/英) |
計算量 / computational complexity |
キーワード(3)(和/英) |
二階多項式 / representations |
キーワード(4)(和/英) |
表現 / second-order polynomials |
キーワード(5)(和/英) |
/ |
キーワード(6)(和/英) |
/ |
キーワード(7)(和/英) |
/ |
キーワード(8)(和/英) |
/ |
第1著者 氏名(和/英/ヨミ) |
河村 彰星 / Akitoshi Kawamura / カワムラ アキトシ |
第1著者 所属(和/英) |
東京大学 (略称: 東大)
University of Tokyo (略称: Univ. of Tokyo) |
第2著者 氏名(和/英/ヨミ) |
スチーブン クック / Stephen Cook / スチーブン クック |
第2著者 所属(和/英) |
トロント大学 (略称: トロント大)
University of Toronto (略称: Univ. of Toronto) |
第3著者 氏名(和/英/ヨミ) |
/ / |
第3著者 所属(和/英) |
(略称: )
(略称: ) |
第4著者 氏名(和/英/ヨミ) |
/ / |
第4著者 所属(和/英) |
(略称: )
(略称: ) |
第5著者 氏名(和/英/ヨミ) |
/ / |
第5著者 所属(和/英) |
(略称: )
(略称: ) |
第6著者 氏名(和/英/ヨミ) |
/ / |
第6著者 所属(和/英) |
(略称: )
(略称: ) |
第7著者 氏名(和/英/ヨミ) |
/ / |
第7著者 所属(和/英) |
(略称: )
(略称: ) |
第8著者 氏名(和/英/ヨミ) |
/ / |
第8著者 所属(和/英) |
(略称: )
(略称: ) |
第9著者 氏名(和/英/ヨミ) |
/ / |
第9著者 所属(和/英) |
(略称: )
(略称: ) |
第10著者 氏名(和/英/ヨミ) |
/ / |
第10著者 所属(和/英) |
(略称: )
(略称: ) |
第11著者 氏名(和/英/ヨミ) |
/ / |
第11著者 所属(和/英) |
(略称: )
(略称: ) |
第12著者 氏名(和/英/ヨミ) |
/ / |
第12著者 所属(和/英) |
(略称: )
(略称: ) |
第13著者 氏名(和/英/ヨミ) |
/ / |
第13著者 所属(和/英) |
(略称: )
(略称: ) |
第14著者 氏名(和/英/ヨミ) |
/ / |
第14著者 所属(和/英) |
(略称: )
(略称: ) |
第15著者 氏名(和/英/ヨミ) |
/ / |
第15著者 所属(和/英) |
(略称: )
(略称: ) |
第16著者 氏名(和/英/ヨミ) |
/ / |
第16著者 所属(和/英) |
(略称: )
(略称: ) |
第17著者 氏名(和/英/ヨミ) |
/ / |
第17著者 所属(和/英) |
(略称: )
(略称: ) |
第18著者 氏名(和/英/ヨミ) |
/ / |
第18著者 所属(和/英) |
(略称: )
(略称: ) |
第19著者 氏名(和/英/ヨミ) |
/ / |
第19著者 所属(和/英) |
(略称: )
(略称: ) |
第20著者 氏名(和/英/ヨミ) |
/ / |
第20著者 所属(和/英) |
(略称: )
(略称: ) |
講演者 |
第1著者 |
発表日時 |
2011-10-21 14:25:00 |
発表時間 |
35分 |
申込先研究会 |
COMP |
資料番号 |
COMP2011-32 |
巻番号(vol) |
vol.111 |
号番号(no) |
no.256 |
ページ範囲 |
pp.25-32 |
ページ数 |
8 |
発行日 |
2011-10-14 (COMP) |
|