解析学における高階計算量  [in Japanese] Complexity Theory for Operators in Analysis  [in Japanese]

Search this Article

Author(s)

Abstract

実数,実数集合,実函数など近似によってのみ表される対象を入出力とする問題について計算量を論ずるための枠組の拡張を提案する.これらの対象を符号化する名として従来しばしば用いられた無限文字列に代えて文字列から文字列への函数(の一部)を用いることにより,より多くの場合に計算量を扱うことができる.これは高階計算量の分野に倣って文字列函数に長さを導入することで,これを入力とする計算に費やす時間ないし空間が「多項式で抑えられる」ことを定義できることによる.これにより計算量級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.

Journal

  • IEICE technical report. Theoretical foundations of Computing

    IEICE technical report. Theoretical foundations of Computing 111(256), 25-32, 2011-10-14

    The Institute of Electronics, Information and Communication Engineers

References:  19

Codes

  • NII Article ID (NAID)
    110008900059
  • NII NACSIS-CAT ID (NCID)
    AN10013152
  • Text Lang
    JPN
  • Article Type
    ART
  • ISSN
    0913-5685
  • NDL Article ID
    023345434
  • NDL Call No.
    Z16-940
  • Data Source
    CJP  NDL  NII-ELS 
Page Top