実函数の計算理論
河村彰星 令和 4 年 7 月 27 日
0 はじめに
計算を理解するための，例えばチューリング機械に基づく枠組は，すべての処理を有限的 な基本単位に分解して考えるという離散的なものである．一方で実世界の課題には勿論，何 らかの量や図形に関する情報という形で実数を含む問題と考えるのが自然なものも多い．そ のような問題の計算可能性や計算量を正確に扱うには，計算の考え方をうまく拡張する必要 がある．計算可能な範囲で実数をはじめとする解析学的対象を扱う分野は，計算可能解析学
（computable analysis）と呼ばれている[16, 2, 11]．
チューリング機械の原論文[14]の標題に「計算可能実数」が現れることからも示唆される ように，計算可能性理論では早くから実数や実函数も興味の対象となってはいた．これを精 密化して時間等の資源を限った「計算量」を考えることも1980年代の葛とフリードマン[8]
に遡ることができるが，理論の整備が進んで様々な対象を扱えるようになってきたのは比較 的最近である．組合せ的な問題の困難さを理解する尺度として確立した，多項式時間Pをは じめとする計算量級やそれらの関係に関する理論を，実数など連続量の絡む問題に応用する のである．本稿ではこの分野の考え方の枠組や典型的な結果について紹介する．実数，実函 数を中心に扱うが，これに限らない空間を考える方法も或る程度は一般的な形で記述する．
以下の基本的諸定義は概ね計算可能解析[16]の分野でよく知られたものだが，計算可能性 のみを論ずる文脈では，計算量を扱い易い形に定式化されていないことがある．計算量の話 題は葛[10]でも扱われているが，後に二型計算量の理論を用いて定式化が改良されており
[5, 7]，本稿でも一部に採り入れている．
0.1
例：計算可能な実函数
計算理論では通常，扱いたい入出力データ（整数，式，グラフなど）を文字列で表し，算法
（algorithm）にこれを処理させる．我々は例えば実数から実数への函数を計算したいから，ま
算法M 実数x
m
n tを2−n 近似する有理数
f(t)を2−m近似する有理数
図1 実函数fを計算する算法M．
ず実数を「表す」必要があるが，これは有限の文字列では表されず，近似によってのみ捉えら れる対象である．数学的に実数を定義する方法の一つは，実数とはどんどん近づいてゆく有 理数の列（コーシー列）であるというものであった．そこで実数を算法に入力するとは，その ような無限の有理数列を与えること，すなわち算法が幾らでも必要な精度でその実数の近似 値を得られるようにしてやることだと考えることにしよう．また算法が実数を出力するとい うのも，利用者からの求めに応じて幾らでも必要な精度でその実数の近似値を書き出すこと と考える．つまり算法Mが実函数f: R→Rを計算するとは，任意のx∈Rについて，もし
•M が質問n∈Nを投げかけると，利用者は|r−x|<2−n なる有理数rの一つを答えて やる
ならば，
•利用者が質問m∈Nを投げかけると，Mは|s−f(x)|<2−n なる有理数sの一つを答え てくれる
ことをいう（図1）．
例えばtriple(x) = 3·xで定まる函数triple: R→Rは計算可能である．これは 1. 利用者「triple(x)を精度 桁で答えてくれ」
2. 算法「ではxを精度 桁で教えて下さい」
3. 利用者「xの近似値（の一つ）は， だ」
4. 算法「triple(x)の近似値（の一つ）は， です」
というやり取りを正しく行う算法があるということである（定義の上では算法が質問を複数 回することも許されるが，今は一遍で足りる）．具体的には，利用者から1.で指定された精 度m∈Nに対して2.で精度m+ 2と指定し，3.で得た近似値q∈Qを使って4.で3·qと答 えればよい．|q−x|<2−(m+2) ならば|3·q−triple(x)|<2−mだからである．
x y
1
−ε +ε x
y 1
図2 実数xが負か正確に判定（左）はできないが，「微妙な場合は誤りを許す判定」（右）は可能．
実数に関する計算ではあるが，個々のやり取りは有限の文字列で表された自然数や有理数 である．「実数に対する演算を基本命令として記述した擬似コード」などと違い，厳密に行い 得る操作のみを定式化した現実的な計算模型といえるだろう．
この現実的制約ゆえに，計算可能な函数は連続なものに限られる．実際，算法は値f(t)の 2−m近似を出力するまでにtの或る2−n近似を知るのみであるから，このような計算が可能 であるには，そもそもtを幅2·2−n の区間に局限しただけでf(t)が幅2·2−mの区間内に局 限されるようになっている必要があり，これは所謂イプシロン・デルタ論法による連続性の 定義そのものである．実数の比較演算，例えば図2左の
F(x) =
1 x <0のとき 0 x≥0のとき
(1)
なる函数F: R→Rは不連続であり，従って計算不能である．比較もできないようでは困る と思うかもしれないが，図2右のように原点からε以内の範囲ではどちらの答を出すことも 許す「多価函数」なら，後で見るように計算可能である．複数ある値のどれを出力しても良 い，という多価函数を考えに入れることが，実数計算では自然に必要になる．
この実函数の計算のような形で外界とやりとりしながら行う情報処理を，二型（type 2）の 計算と呼ぶことがある．零型とは文字列，整数，有限グラフなどのように（有限の）文字列 で表されるデータであり，一型とは零型の対象を入力とする写像や述語，例えば文字列から 文字列への函数とか，整数の集合とかいったデータを指す．実数も上述のように有理数の無 限列（すなわちNからQへの写像）と考えると一型のデータであり，実函数はそれを入出力 とするから二型というわけである．
一型計算の計算可能性や計算量，困難性などについては，例えば文字列を入出力とする チューリング機械などの計算模型を用いて論ずることができた．その議論を二型計算にも拡 張することで，多項式時間などの計算量を考えたり，R以外にも一般的な空間における計算 を扱ったりでき，その方法を述べることが本稿の目的である．以下では，一型計算における 多項式時間やNP困難など計算量理論の基本概念[4]について或る程度は見知っていることを 想定するが，文献による定式化の違いを吸収するため，また二型計算で新たに加わる事柄を 明らかにするため，一型計算と二型計算について並行して理論を組み立ててゆくことにする．
1 問題
計算によって解きたい課題は多くの場合，与えられる入力に対し，何らかの正しい出力を 得たい，という形をしている．例えば，
•二つの素数の積が与えられたとき，その素因数の一方を求めよ
•命題論理式が与えられたとき，それを充足する割当があればその一つを求めよ
•実数xが与えられたとき，tanxを求めよ
といった要求である．与えられ得る入力は無限通りあり，そのすべてに正解することを求め ている．このような要求（をきっちり定式化したもの）を問題（problem）と呼ぶ．入力に対し て出力があるのだから函数のようなものだが，それよりは少し広く捉えた方が良い．という のは，これらの問題では
•二つの素数の積でない数や，充足不能な論理式や，πの奇数倍であるような実数が入力 されたときには，答がない（ので，その場合には正解が要求されない）
•二つの素因数が相異なるときは正解が二つあるし，充足割当が複数あるときにはその数 だけ正解がある（ので，どれを答えても良い）
わけなので，全域函数でなく値が定義されないことがある「部分函数」，また一価函数でなく 値が複数あり得る「多価函数」と一般には考えるべきである．
形式的には，(X, Y)問題（problem）Aは
•集合domA⊆X と，
•各x∈domAに対して集合A[x]⊆Y
で指定される．A:⊆X ⇒ Y のように表すことがある．これは「点x ∈ domAが与えられ たとき，A[x]の元の一つを答えよ」という要求と考えるのである．domAはAの定義域
（domain）ないし約束（promise）と呼ばれる（与えられる入力がdomAに属することを出題者
が計算者に約束しており，計算者はdomAに属しない入力に対する動作について何も保証 しなくてよいという意味である）．つまりdomAが小さくなったりA[x]が大きくなったり すると要求が緩くなる．そこで，(X, Y)問題A，BがdomA⊇domBかつ各x∈domBで A[x] ⊆B[x]を満すとき，AはBの鋭化である，或いはBはAの鈍化であるという．鋭化の 鋭化は明らかに鋭化である．
domA=XであるときAは全域（total）であるという．各x∈domAに対してA[x]が一点 からなるとき，その唯一の元をA(x)で表し，Aは一価（single-valued）である，或いは部分函
数（partial function）であるという．全域かつ一価な問題はすなわち函数（function）である．
(Y, Z)問題Aと(X, Y)問題Bを合成して得られる(X, Z)問題A◦Bとは
dom(A◦B) ={x∈domB:B[x]⊆domA} (2) (A◦B)[x] = [
y∈B[x]
A[y] (3)
で定まるものである．AとBが函数であるときこれは通常の合成である．
問1.1 a，bがそれぞれA，Bの鋭化ならば，a◦bがA◦Bの鋭化であることを示せ．
問題の連続性 0.1節で触れたように，（二型）問題が解けるためにはまず連続であること が必要である．問題とは多価函数であるとしたので，連続性の概念をその場合に拡張しよう．
X，Y を位相空間とする．(X, Y)問題Aが強連続であるとは，任意の開集合V ⊆Y の逆像 A−1V :={x∈domA:A[x]∩V ̸=∅ } (4) がdomAにおいて開（すなわち開集合U ⊆Rが存在してA−1V =U∩domA）であることを いう．Aが函数であるときこれは通常の連続性である．Aが連続であるとは，Aの或る鋭化 が強連続であることをいう1）．
例えば図2右で見た，余裕ε >0のついた比較，すなわち
F[x] =
{1} x≤ −εのとき {0,1} −ε < x < εのとき {0} ε≤xのとき
(5)
で定義される(R,R)全域問題F は強連続である．
問1.2 次の(R,R)全域問題F1（図3左）や(R,R)部分函数F2（図3右）は連続か．
F1[x] =
{1} x <0のとき {0,1} x= 0のとき {0} x >0のとき
domF2=R\ {0} F2(x) =
1 x <0のとき 0 x >0のとき
(6)
問1.3 連続な(Y, Z)問題Aと連続な(X, Y)問題Bの合成A◦Bは連続であることを示せ．
1） これは多価函数を「複数の答のうちいずれを出力してもよい問題」と解する我々の文脈だからこそ適切となる 定義であり，分野によっては多価函数の連続性として異なる定義を採ることもある．
x y
1
x y
1
図3 xが負であるか判定する函数のようなもの．
2 計算可能性と計算量
以下ずっと文字集合Σ上の（有限な長さの）文字列全体をΣ∗ で表す．文脈によっては暗 黙裡にΣ={0,1}としたり，その場に必要な文字を含んでいるものとしたり都合の良いよう に解釈するが，適当に符号化して考えれば議論に差支えはない．
二型計算の入出力はΣ∗ からΣ∗への函数であると述べたが，後で計算量を扱うときの便 宜上，少し制限しておくと都合が良い．（全域で一価な）(Σ∗, Σ∗)函数φのうち，長さ単調
（length-monotone）すなわち|u| ≤ |v|なる任意のu, v∈Σ∗について|φ(u)| ≤ |φ(v)|を満すも の全体を，Σ∗∗で表す．
文字列や文字列函数いくつかをΣ∗∗の一つの元に纏めて符号化する適当な方法を固定して おき山括弧⟨ ⟩で表す．例えば文字列u∈Σ∗はuを値とする定数函数⟨u⟩ ∈Σ∗∗で表したり，
二つの函数φ, ψ∈Σ∗∗は適当な区切り文字#で⟨φ, ψ⟩(w) =φ(w)#ψ(w)などとすればよい．
本節では以下，一型計算としては(Σ∗, Σ∗)問題を，また二型計算としては(Σ∗∗, Σ∗∗)問題 を考える．符号化により他の集合上の計算を考えることについては3節で扱う．
2.1
機械と計算
Σ∗の元を入力とする一型計算と，Σ∗∗の元を入力とする二型計算とについて，並行して話 を進めてゆく．計算手順は厳密には通常チューリング機械などの計算模型で定式化されるが，
その細部は重要でないので，ここでは単に機械と呼ぶことにする．機械は与えられた文字列 を読み取って計算を始め，やがて停止することもあるし，停止せず永遠に動き続けてしまう こともある．停止したときは，書き出された文字列と，費やした時間と空間が定義される．
二型計算ではこのことに加え，冒頭で紹介した実函数の計算のように外界とやり取りをし ながら計算を進める．その様子は神託つきチューリング機械で表される．この機械は読込 テープ，書出しテープ，作業テープの他に「質問テープ」「回答テープ」を具えており，神託 φが入力されているとき，質問テープに文字列uをに書いて「質問状態」に入ると，次の時 刻には回答テープにφ(u)が書き込まれる．が，これもやり取りの仕方の細部は議論に関係が ないので，単に質問uをすると答φ(u)が返ってくるものという理解で概ね差支えない．
神託なし機械と神託つき機械を本稿ではそれぞれ一型機械，二型機械と呼ぶことにする．
これらはそれぞれΣ∗上ないしΣ∗∗上の問題を解く．すなわち，
定義2.1 1. 一型機械M が(Σ∗, Σ∗)問題Aを解くとは，任意のx∈domAに対して或る y∈A[x]が存在し，M に文字列xを与えると（停止して）yを書き出すことをいう．
2. 二型機械Mが(Σ∗∗, Σ∗∗)問題Aを解くとは，任意のφ∈domAに対して或るψ ∈A[φ]
が存在し，Mに神託φと任意の文字列u∈Σ∗を与えると（停止して）ψ(u)を書き出す ことをいう．
これは先述の「domAに属する入力のみに正解すれば良い」「正解の候補の集合A[x]の中 ではどれを答えても良い」という考えに合っている．或る問題を解く機械は当然その鈍化を も解く．何らかの一型機械［二型機械］によって解かれる(Σ∗, Σ∗)問題［(Σ∗∗, Σ∗∗)問題］
の全体をComputableで［Computableで］表す．なおAが函数（や部分函数）である場合，
「函数Aを解く」は語呂が悪いので代りに「計算する」と言うこともあるが，同じ意味である．
部分函数A∈Computableとφ∈domA∩Computableに対し，A(φ)∈Computableである．
解決不能な問題（どの機械によっても解かれない問題）は，例えば対角線論法によって作 ることができる．停止問題（機械を表す文字列xが与えられたとき，機械xに文字列xを与 えると停止するかどうかを1か0かで答える）は，Computableに属しない．
2.2
計算量
問題Aを解く機械Mとしてどれほど効率の良いものが存在するかによって，問題Aの解 き易さを測るのが計算量（計算複雑度）の理論である．
一型計算においては，計算にかかる時間や空間が，入力される文字列の長さの多項式で抑 えられることを以て「多項式時間」や「多項式空間」が定義される．二型計算についても同 じことをしたいが，今度は入力が文字列函数であるから，その「長さ」の概念がまず要る．
φ∈Σ∗∗の長さ|φ|: N→ Nを|φ|(|u|) =|φ(u)|で定義する．本節冒頭のΣ∗∗の定義によりφ は同じ長さの文字列を同じ長さの文字列に移すので，この定義は意味をなす．
この長さ（と言ってもN上の函数）に関する「多項式」で時間・空間を制限したい．それ には二階多項式（second-order polynomial）を用いると良いことが知られている[12, 5]．一型 変数Lと零型変数nに関する二階多項式は以下で帰納的に定義される．
•正整数は二階多項式である．
•変数nは二階多項式である．
•二階多項式P，Qに対し，P +QおよびP ·Qも二階多項式である．
•二階多項式P に対し，L(P)も二階多項式である．
例えば
L L(n·n)+L L(n)·L(n)+L(n) + 4 (7) は二階多項式である．二階多項式P は明らかな解釈により，函数L: N→N を新たな函数
P(L) :N→ Nに移す函数を定めるので，その函数をもP と書くことにする．例えばP が上
記(7)の二階多項式でありL(x) =x2のとき，P(L)は
P(L)(x) = (x·x)22+ (x2·x2)2+x2+ 4 = 2·x8+x2+ 4 (8) なる函数である．この例のように，Lが（通常の一階）多項式であればP(L)も多項式であ る．これを用いて定義される以下の多項式時間計算可能性は，通常の（一階の）多項式時間 計算可能性を保つ自然な二階への拡張になっており，良い性質をもつ頑健な概念となる．
定義2.2 1. 一型機械Mが多項式時間であるとは，多項式p: N→Nが存在して，任意の u∈Σ∗に対し，Mにuを与えると（停止して）計算時間がp(|u|)以内であることをいう．
2. 二型機械Mが多項式時間であるとは，二階多項式P: (N→N)→(N→N)が存在して，
任意のφ∈Σ∗∗とu∈Σ∗とに対し，Mに神託φと文字列uを与えると（停止して）計 算時間がP(|φ|)(|u|)以内であることをいう．
多項式空間も，計算時間の代りに空間を数えて同様に定義する．
定義2.3 1. 多項式時間の一型機械によって解かれる(Σ∗, Σ∗)問題全体をFPで表す．
2. 多項式時間の二型機械によって解かれる(Σ∗∗, Σ∗∗)問題全体をFPで表す．
多項式空間についても同様にFPSPACE，FPSPACEを定義する．
空間を新たに消費する（チューリング機械がテープ上を一歩動く）にも一定の時間がかか るから，多項式時間の機械は多項式空間であり，従ってFPやFPはそれぞれFPSPACEや
FPSPACEに含まれる．これらのように問題を機械による解き易さで分類した集まりを計算
量級（complexity class）という．二型の級FP，FPSPACEは対応する一型の級を保つ．すなわ ち例えば部分函数A∈FPとφ∈domA∩FPに対してA(φ)∈FPである．
なお(Σ∗, Σ∗)問題の集まりであるFPやFPSPACEの代りに，(Σ∗,{0,1})函数すなわち
「判定問題」に考察の対象を絞り，それらのみから成るPやPSPACEを考える文献も多い2）． その場合，機械は1（真）や0（偽）という文字列を書き出す代りに「受理」「拒否」をするとい う言い方をすることもある．これに倣って二型計算においても機械は受理・拒否を判定する のみとし，Σ∗∗の函数のうち値が0か1のみであるもの全体をΣ0-1∗∗ として，(Σ∗∗, Σ0-1∗∗)問題 の集まりPやPSPACEを考える，という形で定義2.3を述べたとしても計算の複雑さを類別 2） FPなどにFが付いているのは述語ではなく函数（function）から成るという意味である．もっとも正確には本
稿では全域で一価な函数ではなく問題の集まりである．
する上でさほど本質的な損はないのだが，ここでは出力も一般の文字列としておいた．これ は，我々は0.1節で触れたようにΣ∗∗の元を実数など何らかの対象を表す名として用いたい ので，入出力がΣ∗∗という形に揃っていた方が少しばかり扱い易いためである．
2.3
計算と連続性
集合Σ∗∗は次の自然な意味で位相空間である．(Σ∗, Σ∗)部分函数kであってdomkが有限 なもの全体をΛとし，Σ∗∗の元のうちk ∈Λの鋭化（すなわち定義域の拡張）であるもの全 体をBk で表す．神託φ∈Σ∗∗に質問を有限回することで判るのはφがBkに属するという 形の情報である．Σ∗∗には{Bk :k ∈Λ}が生成する位相が入っているものと考える．すなわ ちBk という形の集合任意個の合併を開集合と呼ぶ．この位相において連続な(Σ∗∗, Σ∗∗)問 題全体をContinuousで表す．
Computable⊆Continuousは次のように判る．二型機械Mが(Σ∗∗, Σ∗∗)問題F を解くと しよう．Mは神託φ∈domF と文字列x∈Σ∗を受取り，（停止して）y∈Σ∗を書き出した とする．これが正解なのはF[φ]∩B{(x,y)}̸=∅だからだが，そう結論づけるまでに機械は有限 個の質問により或るk∈Λの情報，φ∈Bkという情報を得たに過ぎない．従ってφに限らず 任意のφ′ ∈BkについてもやはりF[φ′]∩B{(x,y)}̸=∅．すなわちBk∩domF ⊆F−1B{(x,y)}． これが任意のx, y∈Σ∗と任意のφ∈B{(x,y)}について成立つのだから，F は連続である．
この議論は機械が神託から有限の知識しか得ないという事実のみに依っており，計算能力 は関係なかった．従って，機械に補助情報として，例えば入力であるφに加えて神託θ∈Σ∗∗
を与えても変らない．Mを神託を二つ受取る機械として，その片方をθ∈Σ∗∗に固定して得 られる（あと一つの神託を受取る）二型機械をMθで表す．
定理2.4 (Σ∗∗, Σ∗∗)問題F が連続であるには，或る機械Mと神託θが存在してMθがF を 解くことが必要十分である．
証明 十分性は上述の通り．必要性を示す．Bk∩domF ⊆F−1Blなる組(k, l)をすべて並べ た無限列（をΣ∗∗ の元として符号化したもの）をθ ∈Σ∗∗ として用いる．機械Mθは神託 φ∈domF と文字列u∈Σ∗を受取ると，次のようにすればよい．各i= 0, 1, . . .に対して順 に(ki, li)を，θに現れる組であってφ∈Bkかつli がl0, . . . , li−1の鋭化でありdomli ⊇Σ≤i なるもの（F の連続性より存在する）の一つ（例えば最初のもの）とする．i≤ |u|まで計算
が済んだらl|u|(u)を出力する． ■
系2.5 連続な(Σ∗∗, Σ∗∗)問題は連続な一価鋭化をもつ．
これは空間Σ∗∗のもつ性質であり，例えばRにおいては図2右（式(5)）のように，連続な 一価鋭化をもたない連続な(R,R)問題が存在するのであった．
3 表現と計算
前節で扱った(Σ∗, Σ∗)問題や(Σ∗∗, Σ∗∗)問題を用いて実数など他の対象に関する計算を論 ずるには，その対象を符号化する方法を決めてやることになる．
3.1
表現
集合X のΣ∗表現（representation）［Σ∗∗表現］とは(Σ∗, X)部分函数［(Σ∗∗, X)部分函数］
γ であって全射的すなわち各x ∈X に対し或るu ∈domγ がγ(u) = xを満すものをいう．
この文字列uはxのγ名（name）であるという．全域な(X, Σ∗)問題［(X, Σ∗∗)問題］γ−1を γ−1[x] ={u∈domγ :γ(u) =x}で定める．Σ∗ 表現とΣ∗∗表現を纏めて表現と呼ぶ．任意 の表現γについて，γ◦γ−1は恒等写像であり，γ−1◦γは恒等写像の鈍化である．
例えばNのΣ∗表現として二進法νN がある．これはdomνN ={0,1}∗\ {ε}，νN(0) = 0， νN(1) = 1，νN(00) = 0，νN(01) = 1，νN(10) = 2，νN(11) = 3，…のような表現である（先頭 に無駄な0が付くのは許すことにした）．またQのΣ∗表現νQは（Σは文字0，1，+，−，/を 含むものとして）domνQ ={sx/y: s∈ {+,−}, x, y∈domνN}と
νQ(sx/y) = νN(x) νN(y) ·
1 s= +のとき
−1 s=−のとき (9)
で定まるものである．
表現によって様々な数学的対象を文字列に符号化し，それを機械が入出力するという形で 計算を論ずる．すなわち，γとδをそれぞれ集合X，Y のΣ∗表現［Σ∗∗表現］とするとき，
(Σ∗, Σ∗)問題［(Σ∗∗, Σ∗∗)問題］F が(X, Y)問題Aの(γ, δ)実現（realizer）であるとは，次の 問にある三つの等価な条件のいずれかが成立つことをいう．
問3.1 次が同値であることを示せ．
1. F はδ−1◦A◦γの鋭化である．
2. δ◦F はA◦γの鋭化である．
3. δ◦F ◦γ−1はAの鋭化である．
計算量級Cに属する(γ, δ)実現をもつ(X, Y)問題の全体を(γ, δ)-Cで表す．
3.2
実数と実函数の表現
実数や実函数の表現と，それらの下での計算の例を挙げる．これらの表現が妥当である理 由については次の3.3節でも触れる．
3.2.1 実数
0.1節で大まかに述べたコーシー列のやり取りによる実函数の計算は，次で定義されるR のΣ∗∗表現ρCを使ったものだったと考えることができる．
φ ∈ Σ∗∗ がx ∈ R のρC 名 で あ る の は ，各 n ∈ N に つ い て φ(0n) ∈ domνQ か つ
|νQ(φ(0n))−x|<2−nなるときとする．
0nは0という文字をn回並べたものである．この表現ではφのうち0nの形をした点での値 しか実質的には使わないわけだが，値φ(0n)の方は，小数点以下n桁分程度の精度で実数x を近似する有理数であるから，通常nと同程度以上の長さの文字列となることだろう．
0.1節 で 触 れ た「 三 倍 す る 」と い う(R,R) 問 題triple の 算 法 は ，文 字 列 0m を 受 取 り，質問0m+2 を投げかけ，帰って来た答φ(0m+2) が表す有理数の3倍を書き出すとい うものでった．その所要時間は算法が受取る文字列それぞれの長さである|0m|= mと
|φ(0m+2)|=|φ|(m+ 2)の或る多項式により，従って|φ|とmの或る二階多項式P(|φ|)(m)に より，抑えられるようにできる．従ってtriple∈(ρC, ρC)-FPといえる．
この計算におけるφ(0m+2)のように実数xの近似値として神託から返される答は，xの絶 対値が巨大であることや，そうでなくても無駄に分母や分子が大きい有理数を用いて書かれ ていることにより，mよりもずっと長いかもしれない．その場合には機械に課せられる時間 制限を相応に緩めてやろうというのが，|φ|の二階多項式P(|φ|)(m)で計算量を表す所以であ る．一方で各実数xはそれなりに短いρC名をもち，それに対しても機械は時間内に答を出す ことを求められる．具体的には，有理数の表現νQの定義(9)を見ると，任意のk, n∈Nにつ いて，区間(−2k,2k)にある2−nの倍数はみな長さk+ 2n+ 4以下のνQ名（例えば分母を10n とするもの）をもつから，(−2k,2k)に属する任意の実数は|φ|(n) ≤k+ 2n+ 4なるρC名φ をもつ．そのようなφに対するP(|φ|)(m)は要するにmとkの（一階）多項式である．つま り(R,R)部分函数f が(ρC, ρC)-FPに属するとは，このような名に対しては「出力f(x)に望 む精度」と「入力xの整数部分の桁数」に関する多項式時間で計算が終るという意味になる．
問3.2 1. square(x) =x2なる(R,R)函数squareは(ρC, ρC)-FPに属するか．
2. domsqrt= [0,+∞)，sqrt(x) = √
xなる(R,R)部分函数sqrtは(ρC, ρC)-FPに属す るか．
3. exp(x) = exなる(R,R)函数expは(ρC, ρC)-FPに属するか．
1 0
2−m
2−µ(m)
図4 ([0,1],R)函数fの連続度µ．
Rの表現としてρCの代りに，次の「普通の小数展開」による表現ρbinを考えてみる．
φ∈Σ∗∗が実数xのρbin 名であるのは，φ(ε)∈ {0,1}∗，φ(0), φ(02), φ(03), . . .∈ {0,1}
であって
x= X∞ n=0
νN(φ(0n))·2−n (10)
であるときとする．
残念ながらρbinはあまり良い表現ではない．例えば次によりρbinの下でtripleは計算でき ない（これに対しρCはRの位相にあった良い表現であることを3.3節で見る）．
問3.3 triple∈/(ρbin, ρbin)-Continuousを示せ．
連続な(R,R)部分函数であって定義域が区間[0,1]であるもの全体をC[0,1]で表す．(N,N) 函数µがf ∈C[0,1]の連続度（modulus of continuity）であるとは，|t−t′|<2−µ(m)なる任意 のm∈Nとt，t′∈[0,1]に対して|f(t)−f(t′)|<2−mが成立つことをいう（図4）．
どのf ∈C[0,1]も連続度をもつ．しかも，もし更にf ∈(ρC, ρC)-FPならば，連続度として 多項式をもつ．実際，fの(ρC, ρC)実現を解く機械Mであって時間が二階多項式P で抑えら れるものを取り，多項式qをq(n) = 2·n+ 4で定めると，µ(m) =P(q)(m+ 1)なる多項式 µ: N→Nはfの連続度である．何故なら，問3.2の直前と同様3）に有理数の表され方を考え ると，|t−t′|<2−µ(m)なる任意のt，t′ ∈[0,1]は，それぞれ長さq以下のρC名φ，φ′ であっ て，長さµ(m)以下のすべての文字列uでφ(u) =φ′(u)なるものをもつ．Mに神託φと文字 列0mを与えた場合と，神託φと文字列0mを与えた場合は，ともに時間µ(m)以内に停止す るので全く同じ結果となり，同一の文字列vを出力する．f(t)とf(t′)はともにνQ(v)から距
離2−(m+1)未満にあり，従って互いに距離2−m未満にある．
3） ここではそのときの議論における「整数部分の桁数」kが0の場合を考えていることになる．kも残して考え ることで[0,1]上ではなくR上の函数にも拡張できなくはないが，話が少し煩雑になるので本稿では今後は主に C[0,1]の函数を考えることにしておく．
C[0,1]の函数が(ρC, ρC)-FPに属することは，多項式の連続度をもち，しかも有理数の入力 に対して多項式時間で近似できることとして次のように特徴づけられる．
定理3.4 f ∈C[0,1]が(ρC, ρC)-FPに属するには，次を満す多項式µと函数φ∈FPが存在 することが必要十分である．
•µはfの連続度である．
•各n∈Nとu∈domνQについてφ(0n, u)∈domνQかつf(νQ(u))−νQ φ(0n, u)<2−n． 問3.5 定理3.4を示せ．
3.2.2 実函数
C[0,1]のΣ∗∗ 表現δC を次で定義する．但し非減少な(N,N) 函数µを表す文字列函数 µ∈Σ∗∗をµ(u) = 0µ(|u|)で定める．
非減少(N,N)函数µとφ∈Σ∗∗の組⟨µ, φ⟩がf ∈C[0,1]のδC名であるのは，µとφが 定理3.4の二条件を満すときとする．
任意のf ∈C[0,1]が確かにδC名をもつことに注意せよ．ここでφをΣ∗∗から取るには，長 さ単調にするために有理数の分母・分子の先頭に無駄な0を付けるなどして水増しする必要 があるかもしれないが，それは簡単にできるため議論に影響はない．今後このようなことは 一々断らないことにする．定理3.4から直ちに，
補題3.6 f ∈C[0,1]が(ρC, ρC)-FPに属するには，fがFPに属するδC名をもつことが必要 十分である．
後の定理3.15においてもδCはρCから自然に定まる表現であることを見る．
問3.7 (C[0,1]×R,R)部分函数applyをdomapply= C[0,1]×[0,1]とapply(f, x) =f(x) で定義する．apply(f, x)∈([δC, ρC], ρC)-FPを示せ．
但しγ0とγ1がそれぞれX0 とX1の表現であるとき，[γ0, γ1]は自然に定まるX0×X1の 表現，例えば次で与えられるものである．
dom[γ0, γ1] ={ ⟨φ0, φ1⟩:φ0∈domγ0, φ1 ∈domγ1} (11) [γ0, γ1](⟨φ0, φ1⟩) = (γ0(φ0), γ1(φ1)) (12) 問 3.8 与 え ら れ た 実 函 数 の ，中 間 値 の 定 理 か ら 保 証 さ れ る 零 点 を 求 め る 問 題 に つ いて考えよう．(C[0,1],R) 問題zero を，domzero ={f ∈ C[0,1] : f(0)·f(1) < 0}と zero[f] ={x∈[0,1] :f(x) = 0}で定める．zero∈/(δC, ρC)-Continuousを示せ．
問3.9 代りに零点がちょうど一つであるときに限った問題を考えよう．zeroの定義域を，
domzero1 ={f ∈domzero : #(zero[f]) = 1}に制限して得られる問題zero1 を考える．
zero1 ∈(δC, ρC)-Computableを示せ．
3.3
翻訳と適格表現
同じ集合のΣ∗∗表現γ1，γ2について，(Σ∗∗, Σ∗∗)問題γ2−1◦γ1は，与えられたγ1名から同 じ意味のγ2名を求める「翻訳」を表す．この問題γ2−1◦γ1が級Cに属するときγ1 ≤Cγ2と書 くことにする．これは「γ1はγ2よりも強い（豊かな情報をもつ）符号化法である」と読める．
(X, Y)問題を解こうとする機械の立場からすると，入力であるXの元は強い表現で与えて
貰えると助かるし，出力であるY の元は弱い表現で書ける方が楽である．すなわちγ1 ≤Cγ2
かつδ1 ≤C δ2 ならば(γ2, δ1)-C ⊆ (γ1, δ2)-Cが（Cが合成について閉じていれば）成立つ．
γ1≤Cγ2かつγ2≤Cγ1なる表現γ1とγ2はC等価（equivalent）（γ1 ≡C γ2）であるという．
問3.10 これまで実数はコーシー列としてきたが，もう一つのよく知られた実数の構成法 であるデーデキント切断の考えに基づく表現を考えよう．Rの表現ρD を次で定義する．
φ∈Σ∗∗とM ∈Nを（MがM桁程度の長さで表されるように）Σ∗∗に符号化した組⟨φ,0M⟩ がx∈RのρD名であるのは，x∈[−2M,2M]であって各n∈Nとw∈Qについて
φ(0n, w) =
1 x > νQ(w) + 2−nのとき 0 x < νQ(w)−2−nのとき
(13)
を満すときとする（右辺の二つの分岐はすべての場合を尽していないことに注意）．すなわち φは，xが有理数νQ(w)よりも大きいか否かを，差が2−n 以下という際どい場合以外は正し く判定する函数というわけである．ρC≡FPρDを示せ．
問3.11 問3.3のρbinを修正して，φ(0), φ(02), φ(03), . . .を{0,1}でなく{0,1,−1}の元とし たものをρsbinで表す．ρC≡FP ρsbinを示せ．
問3.12 Rの単射な表現ρであってρ≡ContinuousρCなるものはあるか．
最弱表現としての特徴づけ
位相空間X のΣ∗∗表現γが（位相的に）適格（admissible）であるとは，γ とγ−1がともに 連続であることをいう．γ，δがそれぞれX，Y の適格な表現であるとき，(X, Y)問題Aが連 続であることとAが連続な(γ, δ)実現をもつことは同値である．
問3.13 ρCは適格であり，ρbinは適格でないことを示せ．
問3.14 位相空間XはT0であるとする．すなわち点x∈X ごとにそれを含む開集合全体が 異なるとする．またX は第二可算であるとする．すなわちX の開集合の可算集合Oが存在 し，X のどの開集合もOの或る部分集合の合併であるとする．このとき次のことを示せ．
1. X は適格な表現をもつ．
2. X の連続な表現γが適格であるには，Xの任意の連続な表現γ′についてγ′≤Continuousγ であることが必要十分．
このように適格な表現とは連続な表現のうち最弱（余計な情報をもっていない）のもので あり4），問3.14の仮定の下でそのような表現の≡Continuous同値類が唯一つ存在する．
3.2.2節で定義したC[0,1]の表現δCも，次のように（Rの表現としてρCを選んだ上では）
函数適用apply（問3.7）が計算できる最弱の表現として特徴づけられる．
定理3.15 C[0,1]のΣ∗∗表現δに対し，apply∈([δ, ρC], ρC)-FPとδ≤FPδCは同値．
4 帰着と完全問題
帰着や困難性の概念を二型計算に拡張し，それを用いて実数や実函数を入出力とする色々 な計算の難しさを論ずる方法について幾つかの例を見る．
4.1
帰着
問題A，Bの難しさを比べるために，「Bが解けるとすると，それを用いて容易にAが解け る」という帰着の概念がよく使われる．
定義4.1 1. A，B を(Σ∗, Σ∗)問題とする．AがB に多項式時間帰着する（A≤FP B）と は，函数r，s∈FPが存在し，任意のu∈domAに対してs(u) ∈domBとなり任意の w∈B[s(u)]についてr(u, w)∈A[u]となることをいう（図5左）．
2. A，Bを(Σ∗∗, Σ∗∗)問題とする．AがBに多項式時間帰着する（A≤FPB）とは，函数r， s∈FPが存在し，任意のφ∈domAに対してs(φ) ∈domBとなり任意のθ∈B[s(φ)]
についてr(⟨φ, θ⟩)∈A[φ]となることをいう（図6）．
Aの入力をBの入力に変換する函数rと，Bの出力をAの出力に変換する函数sを使って 正しく計算ができるということである．
なお「Bを用いてAを解く」の正確な意味をどう定めるかによって，帰着にも色々な変種
4） これを適格の定義とすることも多い[13]．
B
A
s r
u v∈A[u]
A≤FPB
B
A r
u v∈A[u]
A≤FPT B 図5 (Σ∗, Σ∗)問題A，B間の帰着.
B
A
r s
(ψ∈A[ϕ]) y ϕ(y)
x ψ(x)
A≤FPB
図6 (Σ∗∗, Σ∗∗)問題A，B間の帰着．
が考えられる．上記の一型問題間の帰着≤FPはレヴィンの帰着と呼ばれることがある．二型 問題の帰着≤FPは，多項式時間という制限を除けばワイラオホの帰着[15, 1]と同じ形であ る．多項式時間ワイラオホ帰着≤FPは一型の帰着≤FPに形の上では似ているが，神託機械を 用いる点では≤FPよりも強い図5右のチューリング帰着≤FPT にも似ている．以上の帰着はい ずれも推移的である．また次のようにこれらの帰着に関して各計算量級は閉じており，確か に不等号の示唆する「Aの難しさはB以下」という解釈ができる．
補題4.2 1. CをFP，FPSPACEのいずれかとする．(Σ∗, Σ∗)問題A，BがA≤FPBを満 すとき，もしB ∈CならばA∈C.
2. CをFP，FPSPACEのいずれかとする．(Σ∗∗, Σ∗∗)問題A，BがA≤FPB を満すとき，
もしB ∈CならばA∈C.
4.2
完全問題
計算量級Cに対し，問題BがC困難（hard）であるとは，任意のA∈CについてA≤FPB であることをいう．更にB自身がCに属するとき，BはC完全（complete）であるという．
次のFPSPACE完全問題は，一型のよく知られた FPSPACE完全問題をそれぞれ相対化
（適切な意味で神託を附加）したものであり，完全性の証明もほぼそのまま通用する（例えば qbf2 の「穴あき量化命題論理式」を「量化命題論理式」として得られる(Σ∗, Σ∗)問題qbf はFPSPACE完全である）．2.2節末尾と同じくΣ∗∗の函数のうち値が0か1のみであるもの 全体をΣ0-1∗∗ とする．
定理4.3 次の(Σ∗∗, Σ∗∗)部分函数space2, power2, qbf2はFPSPACE完全である．
•domspace2は機械M，単調非減少な(N,N)函数µ，函数φ∈Σ∗∗の三つ組⟨M, µ, φ⟩で あって各u∈Σ∗に対しMは神託φと文字列uを与えられると空間µ(|u|)以内で停止す るものからなる．この三つ組に対してspace2(⟨M, µ, φ⟩)(u)は，このMの計算の出力．
•dompower2は長さを保つ（各n∈Nで|f|(n) =nなる）f ∈Σ∗∗ からなる．このfと 文字列uに対してpower2(f)(u) =f2|u|(u)．
•domqbf2 =Σ0-1∗∗．各p∈Σ0-1∗∗ と文字列vに対してqbf2(p)(v)は，vが穴あき量化命題 論理式でvpが真であるとき1，さもなくば0とする．
但し穴あき命題論理式とは，命題論理式の帰納的な作り方において通常の論理結合子に加 え，論理式fi1, . . . , fin から□(fi1, . . . , fin)を作ることを許したものである（nは一定でなく てよい）．穴あき命題論理式uとp∈Σ0-1∗∗ に対し，uに現れる□をpとして解釈すると，後は 命題変数の値を決めると真偽が決るようになる．こうして得られた命題函数をupで表す．例 えばuが穴あき命題論理式
□(X1)∨ ¬X2∧□(X2,¬X1) (14) であってpがp(0) = 0，p(1) = 0，p(0,0) = 0，p(0,1) = 1，p(1,0) = 1，p(1,1) = 1を満す とき，up: {0,1} → {0,1}は，(X1, X2) = (0,0)のときのみup(X1, X2) = 1，その他のとき
up(X1, X2) = 0となる函数である．穴あき量化命題論理式とは，穴あき命題論理式の先頭に，
それに現れる命題変数すべてに対する量化子（∀か∃）を付けたものであり，その真偽は明ら かな方法で定める．例えば穴あき量化命題論理式vを
∀X2.∃X1.□(X1)∨ ¬X2∧□(X2,¬X1) (15) とし，pは上記のものとすると，vpは偽である．
