補問題の難しさって何だろう?

さて,僕が今所属している研究室では,グラフ理論と計算可能性を扱っています.
計算可能性とは大雑把に言うと,「問題がどのくらい難しいのか」を証明する理論です.
そこに,「補問題」というものがあります.補問題とは,元の問題と逆の問題のことです.
あ,別に難しい話をしようって言うんじゃないんですよお客さん.

例えば,「ニワトリは飛べる,は正しいか?」という問題があったとします.
これにYesと答えるには,飛べるニワトリを1羽見つけてくればいいことになります.
一方,補問題は「ニワトリは飛べない,は正しいか?」という問題になります.
これにYesと答えるには,世界中のニワトリを調べて,飛べないことを確認しなくてはなりません.

つまり,片方の問題では例を1つ見つければよいけれど,他方ではしらみつぶしに全部調べないと答えられない,ということです.
これは,計算可能性で言うところのNPとco-NPの関係に相当します.

同様に,現実でも,ある質問は返答しやすいけれど,その逆を取ると返答が困難になるということはないでしょうか?

例えば,お店で「なんでこの商品は安いの?」と聞かれたら,流通コスト削減だとか仕入れがどうとか,なんとでも応えられそうです.
しかし,逆に「なんでこの商品は高いの!」と聞かれたらどうでしょう?
仕入れから販売まで全てのコストを説明しないとその値段に納得してもらえないかもしれません.

ここでも,前者はたくさんある理由のうち,どれを取っても答えになりますが,後者は全てを説明し尽くさなくては答えにならない,という関係があるわけです.

まだまだ,こんな問題はいくらでも考えることができそうです.
「宇宙人は存在するか?」とか,「永久機関は作ることができるか?」とか,いくらでも思いつきそうです.
そして,往々にして補問題型の論法に対して,人は答えを見つけられなくてハマりやすいんじゃないかと思います.

もし,はっきり分からないことを言われて迷った時には,その逆は何だろう?と考えてみるといいのかもしれません.
その補問題を考えてみると,意外と簡単なことなのかもしれないデスよ?

Author: _fp

Software Engineer Place: Tokyo, Japan Skills: C, Javascript, Objective-C, Perl, Clojure, Java, PythonErlang, Haskell, OpenGL Twitter: _fp