忍者ブログ

Memeplexes

プログラミング、3DCGとその他いろいろについて

タイムマシンコンピュータを利用してNP完全問題を多項式時間内に解く その２

以前の記事でTodd A. Brunさんの論文を紹介しました。

タイムマシンコンピュータを利用してNP完全問題を多項式時間内に解く

この論文はある種の難しい計算問題をあっというまに解いてしまう方法を示しています。
ただし、その方法を行うにはタイムマシンがなければいけません。

その後私はもう少しスマートな方法を思いつきました（自画自賛ですが）。
プログラムがより単純で済む上、Todd A. Brunさんのオリジナルの方法よりも、必要とされるタイムトラベルの条件が圧倒的に緩いです（自画自賛ですが）。
もうすでに誰か別の人が同じことを考えついているような気もしますが、念のためメモしておきます。

なお、この記事は以前の記事の内容をベースにしているので、まだ読んでいない方は以下の記事からお読みください。


願望成就機械の特殊ケース

以前の記事「願望成就機械」を読まれた方はお気づきでしょうが、これは叶えたい願望を「このNP完全問題の答えを知りたい」にすれば、NP完全問題の答えが多項式時間内に求まります。

プログラム

using System;
using System.ClosedTimelikeCurves;

class Program
{
    static void Main()
    {
        TimeMachine<int> timeMachine = new TimeMachine<int>();
        int answer = timeMachine.FromFuture();

        if (!isAnswerCorrect(answer))
        {
            neverBeExecuted();
        }

        Console.WriteLine(answer);
        timeMachine.ToPast(answer);
    }

    static void neverBeExecuted()
    {
        TimeMachine<bool> timeMachine = new TimeMachine<bool>();
        bool value = timeMachine.FromFuture();
        timeMachine.ToPast(!value);
    }

    static bool isAnswerCorrect(int answer)
    {
..
    }
}

このプログラムは、isAnswerCorrect()メソッドで正しいと判断された答えを求めます。
isAnswerCorrect()で判断する答えがNP問題のものなら、多項式時間内にこのプログラムは正解を導き終了します。

何をやっているのか見て行きましょう。
このプログラムはどこからか怪しげな正体不明の情報を持ってきて（この場合は未来から）、その情報が解きたい問題の正解になってなかったらタイムパラドックスを意図的に引き起こします。
いえ、正確には意図的に引き起こそうとします。
しかしながら当然タイムパラドックスなど現実には起きないので、出所不明のその情報はNP問題の答えになっていなければなりません。
この情報は必ずNP問題の答えなのです。

なお、ここではTimeMachine<T>クラスを２ヶ所で使っていますが、片方は怪しげで正体不明の値がほしいから使っているだけなので、実際には１か所で構いません。
正体不明さを保証できるのなら、他のものでも構いません。
なんならサイコロを振って情報を適当に取得しても構いません。

別解

using System;
using System.ClosedTimelikeCurves;

class Program
{
    static void Main()
    {
        QuantumRandom random = new QuantumRandom();
        int answer = random.Next();

        if (!isAnswerCorrect(answer))
        {
            destroyUniverse();
        }

        Console.WriteLine(answer);
    }

    static void destroyUniverse()
    {
        TimeMachine<bool> timeMachine = new TimeMachine<bool>();
        bool value = timeMachine.FromFuture();
        timeMachine.ToPast(!value);
    }

    static bool isAnswerCorrect(int answer)
    {
..
    }
}

このプログラムも上のプログラムと同じ働きをします。
どんなNP問題も多項式時間内に解いてしまいます。

さっきのプログラムと違うのは、量子サイコロを振ってint型の値を決めているところです。
このサイコロの結果は、NP問題の正しい答えにならざるを得ません。
ハードウェアが実行中に爆発すれば話は別ですが。

さて、このプログラムは機能としてはさっきのプログラムと同じですが、では物理現象のレベルではどうでしょう？
さっきのプログラムで使ったのはclosed timelike curveでなにもないところから（？）勝手に出てきた情報です。
一方こっちは、量子サイコロをふった結果です。
両方共ランダムですが、この２つの間には何か物理的な関係があるのでしょうか？
残念ながら私の物理学に関する聞きかじりの薄っぺらい知識だけでは答えはわかりません。
いちおう、次の論文がなにか関係有るような気がしなくもないような気がします（と言っておきながら私はタイトル以外まだまともに読んでません）。

A Gravitational Explanation for Quantum Mechanics
The Logic of Quantum Mechanics Derived from Classical General Relativity

そういえばグレッグ・イーガンさんのSF小説『百光年ダイアリー』でも量子力学的なランダムとclosed timelike curvesの関係についてちょこっと言及が合った気がしますね。

この方法の利点

この方法にはTodd A. Brunさん方式と比べて２つの利点があります。
（Todd A. Brunさんをディスってるわけじゃないですよ。念のため）

  1. 必要とされるclosed timelike curveの規模が極めて小さくて済む
  2. プログラムがよりシンプルになる

必要とされるclosed timelike curveの規模が極めて小さくて済む

Todd A. Brunさん方式では、かなり大規模なclosed timelike curveを作れなければなりません。
もし正攻法でNP問題を解くのに100年かかるのなら、100年前まで戻るclosed timelike curveを作れなければいけないのです。
実際に使われるclosed timelike curveは答えの正否をチェックするための多項式時間分戻るだけです。
しかし、タイムパラドックスを起こせる可能性を残すため、決定性チューリングマシンで100年かかるNP問題を解きたいなら、closed timelike curve生成装置は100年前まで情報を戻せなければいけません。
現実には使われないのに、大きな規模のclosed timelike curveを作れなければいけないのです。
そしてその規模のオーダーは多項式では済みません。
問題の規模が大きくなると、もっと急激に必要とされるclosed timelike curveの規模が増えていくのです。
そのような大規模なclosed timelike curveを作るのに必要とされるテクノロジーは、現在の私達からすれば想像を絶する物になるでしょう。

（※追記（2015/01/24）
すみませんこれは多分間違ってます。
テクノロジー自体はたいして必要ありません。
一秒前に情報を送れるclosed timelike curve発生装置を作れるならば、それらをいくつか組み合わせて思う存分過去へ情報を遡らせることが可能です。
作れるclosed timelike curveの規模とその生成のための準備期間の長さにもよりますが、ある一定の数のCTC発生装置を作れれば一気に無限への扉を開けます。
全く同じ話がSF小説『The Arrows of Time』にありましたね。
必要なのは想像を絶するテクノロジーではなく、十分な額の金です。）

しかしこの記事の方法では、必要とされるclosed timelike curveは非常に小さくて構いません。
1ミリ秒前に情報を戻せるだけでいいのです。
そして、その時間は定数です。
o(1)です。
問題の規模がどんなに大きくなっても、必要とされるclosed timelike curveの規模は変わりません。

しかもTodd A. Brunさん方式と違って、戻すのは1ビットだけです。
以前紹介したサンプルプログラムだとTodd A. Brunさん方式で過去に送る情報は32bitですね。
情報源には普通の量子サイコロを使えるので、closed timelike curveをたくさん用意する必要はありません。
（とはいえ、ハードウェアが故障する可能性もあるのでたくさん作って故障耐性を持たせる必要はあるでしょう）

プログラムがよりシンプルになる

Todd A. Brunさん方式では、ユーザーは2つのメソッドを書かねばなりませんでした。

  1. 答えが正しいかチェックするメソッド
  2. NP問題を決定的チューリングマシンで解くメソッド

2は実際に実行されることはありません。
にも関わらず、正しい答えを得るためには書かなければいけませんでした。
しかしそれって、ちょっとめんどくさいですよね。

この記事の方式だと、1だけで構いません。
2はいらないのです。
2の代わりに、「論理の力だけで自分を実行しているハードウェアを破壊するプログラム」を使うのです。
そしてそれは、たったの3行です。

※追記 (2015/2/18)
よく考えるとBrunさんのアルゴリズムにはこのエントリーのアルゴリズムにはない良い所があることに気が付きました。
それはBrunさんのアルゴリズムは、「タイムトラベラーはこの宇宙の過去へ行くのではなく、別の宇宙の過去に行くのだ」という、デイビッド・ドイッチュの考えが正しかったとしても、うまくいく可能性があるという点です。
必ず成功するとは限りませんが、ハードウェアの故障耐性を高めておけば、仮に他に無限の宇宙があったとしても、別の宇宙でもコンピュータは同じ状態のなのでうまくいくでしょう。

一方このエントリーのアルゴリズムは、タイムトラベラーが別の宇宙に行くケースでは、上手く動く見込みは全くありません。
デイビッド・ドイッチュの理論は、この種の単純なタイムパラドックスを完全に解消し、無力化してしまいます。
そういうわけで、どっちのアルゴリズムが良いのかというのは、タイムトラベラーがどの宇宙に行くのかということに依存するでしょう。

拍手[1回]

PR