「NPより上の世界の別解問題」に関する注意 (2004.1.1)

「NPより上の世界の別解問題」 の著述にあたっては伊藤剛志、八登崇之の両氏との相談がなされ、 また、彼らの結果というべきものも多く含みます。
伊藤氏の意見により、ASP G3のEXPTIME完全性が証明されていることに気づかされました。 氏の意見が無ければ、 「解の長さが指数的になることがあっても、短い解で変換に成功していれば関係ない」、 ということにはまだ気づいていなかったかもしれません。
八登氏には、変換の正しさのチェックなどで相談にのっていただきました。 (加えて、氏はこれに先立つNPの世界での別解問題の研究において共同研究者です。)
また、結局意思が続かず、いまだ達成できずじまいですが、 自分の書きたいことを書ききったら、両氏に意見をもらおうと思っていました。
というようなことで、共著の論文として公開したかったのですが、 完成した文章という意識がないため、著者名を入れる気にならず、
かといって、いくら結果が予想通りで、やれば出来そうなことしか書いていなくても、 せっかくこのページにたどりついた方に読ませることなく 握りつぶしてしまってよい程には下らなくもないと思うので、 著者欄を空にした上で、ここに公開しておきます。
もともと2003年8月に完成させたかったのに書く気がおきなかったのだから、 僕(瀬田)が大学に在籍する間にこれ以上書くことは無いと思われますが、 NPの世界での「ASP完全」に対応することがG3に対しても起きているのか、には興味があるし、 今は書けないけれど、時間と気力とがあれば、せめて、当初書くつもりでいたことまでは書いて、 どこか別の場所で公開できたら良いと思います。