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

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

育児の合間に新しいネタを仕上げつつあります．（他にも科研費の報告書書きやらジャーナル投稿論文の修正作業やらあるのを尻目にですが・・・）九割方証明を終えてはいるのですが，いつも残り一割に落とし穴があるのです．慎重に詰めていかねば．しかしFOCS…

Trevisan のとこの博士課程学生の James Cook がかの Stephen Cook*1 の息子だったとは．知らんかった． *1:Cook-Levin Theorem の Cook です．

やはりあと一歩のところでダメでした．でもアプローチとしては悪くなさそうなので，もう少し頑張ってみようと思います．

四半世紀ぐらい未解決の結構有名な予想が解決できた気がします．二日ほどしか考えていないのですが，本当に解決できたのか自分でも半信半疑なので慎重に証明を進めてみようと思います．