NP問題は良く知られているように降下型自己帰着(downward self-reduction)を持ちます．つまり，長さ以下のインスタンスの判定を行うオラクルがあれば，多項式時間で長さのインスタンスの判定を行うことが可能，ということです．分かり易い例でいうと充足可能…

結局残り一割のところにミスが見つかり，まわりまわって結局正しくなりそうなので，さらに証明をつめていく作業に入っています．日中は家事と我が子の世話をしつつ，彼が寝ている隙に研究を進める毎日です．