忍者ブログ

Memeplexes

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

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

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

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

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

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

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


拍手[0回]

PR

タイムトラベルジョーク集

このブログのタイムトラベル関係のジョークの一覧です。
結構数が増えてきたので、まとめてみることにしました。
すべてClosed timelike curveモノで、過去へ戻るとこの宇宙にそっくりな平行宇宙に行く話はひとつもありません。

  1. タイムマシンの正しい使い方・および宇宙の物理法則の書き換え方
  2. タイムマシンコンピュータ System.ClosedTimelikeCurves.TimeMachine(T)クラス
  3. タイムマシンコンピュータを利用してNP完全問題を多項式時間内に解くその2
  4. 論理の力だけで自分を実行しているハードウェアを破壊するプログラム
  5. 自分を死から守るお守り
  6. 願望成就機械


拍手[0回]