Planarity & Directed Acyclic Graph 平面化と有向非巡回グラフ

問題というのは想像以上に低い閾値で難度が爆発する。これは問題のトポロジーに対する論理ステップと、決定アルゴリズムが、spaceとtimeというリソース制約の影響を受けると比較的低い閾値で巡回グラフになりがちだからである。無向、閉路グラフばかりに取り組もうとする大企業内のプロフェッショナルは多い。これは探索爆発に伴う普遍的な認知バイアス、ジレンマと言える。一方、問題を平面化し、出口があることが確定している有向非巡回グラフを描こうとしている人は、予言師のような予測力と魔法使いのようなスキルを持っているように見えるだろうが、この問題は四色定理や三色問題のNP-completeのsatisficingという類型にモデル化することができる。
一方モデル化できるからといって、現実世界で簡単に進むかというとそれはアムダールの法則などの直列プロセスボトルネックによって阻まれる。しかし、DAGであるか、そうでないかどうかはクリティカルな視点である。