計算量演習問1.3でわからない点があったので質問させていただきます。
問題のΩ(lδ^2)には変数がlとδの２つあり、問題文の状況的には、lは無限大に、δは無限小に動かすと解釈できると思うのですが、そうすると、lδ^2全体としては、どちらに動くものとして(1)の主張を表現すればよいのでしょうか?
はい、お気づきの通り二つの変数がそのように動いており、これは問1.1の直前の段落と同様に「或るc≧0が存在し、十分大きなすべてのlと十分小さなすべての正のδについて、…」という意味になります。
で、この「…」に入る不等式が「どちら向き」になるかは、Ω記法についてのそこまでの説明からわかるはず。考えてみて下さい。
回路において、一つの素子の出力が複数の素子に入力されることはあるか。
あります。図にある例もそうなっています。
なお、これを禁じた回路は「論理式」と呼ばれます（→第三回など）。
チューリング機械に或る入力を与えたときの消費空間が s であるとは、k 本の作業テープ全体で s 個の欄を訪れたということか、それとも一本づつ別々に数えてその最大が s 個ということか。
（後者の積りでしたが、）どちらで考えても構いません。
問2.3ではFPが繰返しについて閉じていないことが示されたが、これは繰返しにより指数的に長い文字列が生ずるからだった。では「長ささえ抑えられていればFPは繰返しについて閉じている」という感じのことは言えるのでしょうか。
はい、FPはコバム（A. Cobham）の有界再帰と呼ばれる操作について閉じており（bounded recursion on notation）、これを使って「FPは函数○○を含み合成と有界再帰について閉じた最小の集合である」という特徴づけができます。適当に検索してみて下さい。
Pなどの計算量級は講義で「クラス」と呼ばれているが、これは集合論における「クラス」と関係があるか。
ありません。公理的集合論では、集合（set）とは何であるか厳密に扱うため、その基準に合わない（けど便宜上「ものの集まり」と考えたい）ものをclassと呼びます。漢字に訳するときは「類」とするようです。なお、基準に合わない集まりとは、例えば「すべての集合の集まり」のような、いかにもヤバそうなものであって、この演習に出てくるような集まりは心配無用です。
というわけでPやNPなどは歴とした集合ですが、計算量理論ではそのように問題からなる集合をよく扱うので、他と区別しやすくするため特にclassと呼びます。羊の集合を「群れ」と呼び、議員の集合を「派閥」と呼ぶごとく、何の集合かによって呼び方を変えたい気分になっただけのことです。本演習では、生徒の集合（学級）、滑らかな函数の集合（Ck級）などと同じく「級」と訳しています。
つまり、「set」以外の「集まり」っぽい言葉が欲しかった、という理由で偶然どちらも「class」になっただけであり、それ以上の深い繫がりはありません。
問3.3では、入出力の各数を二進法で書くのか。その場合、テープの左端から上位ビットを先頭にして書くのか。また各数の間はコンマのようなもので区切られているのか。
はい、そう考えて下さい。
しかし例えば数を下位ビットから書くものと考えても結構です。どちらで考えてもあまり影響はありません（特に問3.3の問題がFLに属することには変りがない）。これは、「与えられた文字列をひっくり返した文字列を書き出すことは対数空間でできる」ことと「FLは合成について閉じている（問3.2）」ことからわかります。
多項式空間限定の機械の定義においても、出力テープは空間制限の対象から外すのか。
はい、この演習の資料での定義をそのまま読むと、そういうことになります。といっても本演習では多項式空間限定は判定問題についてしか考えない（PSPACEは定義したが、「FPSPACE」というものは扱わない）ので、どちらでも関係ありません。
しかし実はこのままでFPSPACEを定義してしまうと指数長の出力もできることになり、都合が悪い場合もあります。例えば問2.1と同様のことを成立たせるには、出力も多項式長に限るべきだということになります。
乱択機械の説明で「なおここで乱択機械は各時点で二つの遷移から等確率で選ぶものとしたが，これをうまく利用すると 2 の冪でない n に対しても，n 通りの遷移に概ね等確率で分岐できるので，以下ではこの点は気にせず n 個の遷移をちょうど確率 1/n で選ぶこともできるかのごとく考えてよい」と説明されていますが, 具体的にどのようにして, 1/nで分岐するよう考えることができるのでしょうか?
例えば何かを計算する都合上、機械を5分岐させたい（5通りの動きA、B、C、D、Eを確率1/5づつで行いたい）としましょう。でも厳密にいうと機械は（この演習の定義では）2分岐しかできません。さてどうするか。
2分岐を例えば16回繰返すことで65536分岐することはできます。そこで大体1/5づつの確率になるよう、この65536分岐のうち13107分岐でAを、13107分岐でBを、13107分岐でCを、13107分岐でDを、13108分岐でEを行うことにします（つまり一度5分岐するのに16ステップかかるが、定数なんて気にしない）。すると1/5からは少しずれますが（具体的にはEをやる確率が最もずれて、約0.000006くらい違う）、少しなので計算全体に対する影響は僅かです。どれくらい僅かかというと、例えばこの5分岐という機能を計算全体で最大100回しか使ってないとすると、計算の最終結果が或る値になる確率は最悪でも0.0006しかずれない。ということは、もとの誤り確率が例えば0.25だったのが0.2506に増えるくらいの影響しか出ません。で、そういう違いは気にしなくてよいというのは問4.3や4.8でやりました。
（勿論「5分岐を100回行いたい」以外の場合は、それを見越して「65536分岐」という所を適当に調整して下さい。）
…という議論を一々やるのはシンドイので、まあ等確率で5分岐できると思ってて下さい、ということです。
6-1頁の説明ではMAX-KNAPSACKの入力は整数としてありますが、問6.2では有理数であれば正解としました。
問6.5（1）において「重量 s が文字列 0s として与えられる（価値 v は二進法で書かれる）」としていましたが、逆に「価値 v が文字列 0v として与えられる（重量 s は二進法で書かれる）」として下さい。どちらでも（1）は解けますが、修正した方が（2）への繫がりがよくなります。
この修正に関する措置 修正前後いずれで解いても正解とします。
P＝NPならばPA＝NPAではないのか。
そうは言えません。PAやNPAという書き方においてPやNPは、単なる問題の集合ではなく、それらの集合を定義したやり方（例えばNPなら「多項式時間でN決定」）を指しています。NPAとは、NPを定義したのと同じやり方で、但しただの「機械」の代りに「神託Aのついた機械」を用いたものとして、定義されます。NPという集合に何らかの方法でAを附加して定義されるのではありません。