Holographic algorithm とは

コンピュータサイエンスでは、ホログラフィックアルゴリズムはホログラフィックリダクションを使用するアルゴリズムです。ホログラフィックリダクションは、ソリューションフラグメントの合計が変更されないように多対多のソリューションフラグメントをマッピングする一定時間の短縮です。これらの概念は、Leslie Valiantによって紹介されました。Leslie Valiantは、「その効果は、ソリューション・フラグメント間に干渉パターンを生成するものとして見ることができる」ため、ホログラフィーと呼びました。このアルゴリズムは、比喩的なことを除いて、レーザーホログラフィとは無関係です。それらの力は、ホログラムの干渉パターンに類似して、多くの寄与が相互に相殺されることから生じる。
ホログラフィックアルゴリズムは、充足可能性、頂点カバー、および他のグラフ問題の特殊なケースについて、これまでに知られていた解決策なしに、問題に対する多項式時間解を見つけるために使用されてきた。彼らは、P対NP問題に関連しているとの推測と計算複雑性理論へのそれらの影響のために注目すべき報道を受けている。一般的な問題のいくつかは#Pハードな問題ですが、解決された特殊なケースは自分自身が#Pハードではないので、FP = #Pを証明しません。
ホログラフィックアルゴリズムは、量子計算といくつかの類似点を持ちますが、完全に古典的です。