忍者ブログ

Memeplexes

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

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

この記事はComputers with closed timelike curves can solve hard problemsという論文の紹介をします。


前回、過去へ情報を送り未来から情報を受け取る、TimeMachine<T>クラスの紹介を行いました。
今回はその応用を行なってみようと思います。

TimeMachine<T>クラスの利点の一つに、いかなるNP問題も多項式時間内に解くことが出来る、というものがあります。
NP問題の中にはかなり難しいものもあり、現実的な時間ではまともに解けない問題があります。
しかし、TimeMachine<T>クラスを利用すると、まあ頑張れば解けるレベルにまで落ちます。
このことはTodd A. Brunさんによって論文になっています。
その論文で紹介されているアルゴリズムをわかりやすく紹介します。

背景:世の中には答えを出すのは難しくても、答えが正しいかどうかはすんなりわかる問題がある

ここでの話の背景をわかりやすくまとめます。
(NP完全問題とかいう言葉はどうでもいいです。)
現在、コンピュータのアルゴリズムには、計算の量の膨れ上がり具合によっていくつか種類があるらしいとされています。

1+1=?、これは簡単です。
2×2=?、これもまあ簡単でしょう。
しかし「507473をA×Bの形に分解せよ、ただし、AとBは1より大きい整数である」と言われるとだいぶ困る人が多いはずです。
この問題の答えは509×997です。
しかし、509×997の計算を行うのと、507473をA×Bの形に分解するのとでは、必要な計算の量が違うっぽい、というのはご理解いただけるのではないかと思います。

(最初に足し算とかけ算を引き合いに出しました。
やや卑怯なことに1+1などと1桁の数どうしの計算を例としてあげましたが、この2つの問題が3桁の数同士の計算だったとしても、この分解問題よりはすぐ解けるでしょう)

つまり、世の中には「答えを出すのは難しくても、答えの候補が与えられた時、それが正しいかどうかすぐにチェック可能である」ような問題があるらしいのです。
現在この仮説は正しいとは推測されているものの、正しいと証明はされておらず、もやもやとした感じが残っています。

タイムマシンコンピュータが速く解くことの出来る問題とは?

TimeMachine<T>クラスでどんな問題も速く解けるようになるわけではありません。
TimeMachine<T>クラスで速く解けるようになる問題は、「答えのチェックが簡単な問題」に限られます。
まあそれでも「答え自体を計算するのは長い時間がかかっても、答えの候補が正しいかどうかのチェックはすぐ終わる問題」がすぐ解けるようになるのでよしとしましょう。

ちなみに、「答えのチェックも難しい問題」はお手上げです。
まあお手上げというと言い過ぎですが、正しい答えが手に入る保証はなくなります。

さて、ではTimeMachine<T>クラスを利用して、そのような種類の問題をあっという間に解いてしまうプログラムを見てみましょう。

using System;
using System.ClosedTimelikeCurves;

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

        if (!isAnswerCorrect(answer))
        {
            answer = hardProblem();
        }

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

..
}

このプログラムは、「答えのチェックはすぐ済むが、答え自体を直接計算するのは難しい問題」(「507473をA×Bの形に分解せよ」なんかを思い浮かべて下さい)を、TimeMachine<T>クラスを利用してあっという間に解きます。

このプログラムは、答えを未来から取得します。
そしてその答えがもし仮に間違っていたとしたら、正解をものすごく長い時間をかけて計算します。
そして、答えが確かに正しいことを確実にした上で、過去へ答えを送ります。

さて、ここで面白いのは、「正解をものすごく長い時間をかけて計算する」行は、決して実行されない、という点にあります。
なぜなら、必ず答えが正しいことが確実になった状況で、答えが過去へと送られてくるからです。
未来から送られてくる答えは必ず正しいので、この「正解をものすごく長い時間をかけて計算する」コードは実行されないのです。
にも関わらず、「正解をものすごく長い時間をかけて計算する」行は必要です。
その行がないと、「答えが確実に正しいと言い切れる」ことはありえないからです。
間違った答えが出力される可能性が極めて高いです。
この行は、決して実行されないにもかかわらず、答えに影響するコードなのです。

結局このプログラムの速度を決めるのは、isAnswerCorrect()の実行速度です。
答えのチェックを行うこのメソッドの実行がすぐに終わるなら、答えもすぐに手に入ります。

拍手[0回]

PR