免疫集合と単純集合の計算複雑さ

点击翻译按钮获取中文摘要

本研究において,免疫集合と単純集合についてこれまでに得られた一連の結果をまとめ,フランスでの国際研究集会The 3rd IFIP International Conference on Theoretical Computer Science (TCS2004), August 23-26,2004で発表[2]を行なった(発表講演は共著者のYamakami氏による).その内容は論文[1]として出版された.論文[1]に詳細な証明を付けた完全版を論文[3]として投稿した.また,論文[2]の最終校正を行なった.[1]Toshio Suzuki, Tomoyuki Yamakami,"Resource bounded immunity and simplicity (extended abstract),"In : J.Levy et al.eds., Exploring New Frontiers of Theoretical Informatics, pp.81-95,Kluwer Academic Publishers,2004.ISBN 1-4020-8140-5.[2]Toshio Suzuki,"Bounded truth table does not reduce the one-query tautologies to a random oracle,"Archive for Mathematical Logic,掲載決定.[3]Tomoyuki Yamakami, Toshio Suzuki,"Resource bounded immunity and simplicity,"Theoretical Computer Science,投稿中.