７．時間限定チューリングマシンと 　　クラスP

内容

1. スライド　1 ７．時間限定チューリングマシンと　　クラスP
2. スライド　2 7−１．入力サイズ
3. スライド　3 名称：合成数の問題 インスタンス：整数ｎ 問：ｎは合成数か？
4. スライド　4 一方、グラフの問題では、頂点数や、辺数を入力サイズと みなすことが多い。
5. スライド　5 このインスタンスをチューリングマシンに入力する。
6. スライド　6 練習
7. スライド　7 ７−２．時間限定チューリングマシン
8. スライド　8 テープ数と計算時間
9. スライド　9 証明
10. スライド　10 ヘッド２を右端に移動
11. スライド　11 とし、
12. スライド　12 交差列
13. スライド　13 問題の言語を認識する１テープTMをMとし、その受理動作を 観察する。
14. スライド　14 ここで、これらの事実から、
15. スライド　15 これは、 も認識してしまう。 矛盾である。
16. スライド　16 したがって、テープ中央のセルにおける交差列は、 以上である。
17. スライド　17 ７−３．記号の増加による高速化技法
18. スライド　18 証明
19. スライド　19 アィディア
20. スライド　20 （１）先ず、最初に与えられた０と１の入力列に対して、　 　　それを第二テープに...
21. スライド　21 （２）　　　は　　　のシミュレーションをおこなう。
22. スライド　22 M’は明らかにMの動作をシミュレートできる。 Mが受理状態になるとき、そのとき...
23. スライド　23 M’
24. スライド　24 ７−４．クラスP
25. スライド　25 証明
26. スライド　26 Mの各々のステップに対して､Sはテープの使われて いる部分を2回すべて走査する...
27. スライド　27 Mの一回のステップに対しては、２回Sを走査し、 高々ｋ回のシフト操作を行うだけ...
28. スライド　28 クラスPの定義
29. スライド　29 決定性の計算における計算時間
30. スライド　30 クラスPに属する言語（問題）例
31. スライド　31 ７−５．クラスＰの意義
32. スライド　32 関数の分類（シータ記法）
33. スライド　33 関数の分類（オーダー記法）
34. スライド　34 計算時間と関数
35. スライド　35 関数の概形
36. スライド　36 計算機科学の目的