国際会議SAT2016の予稿集、7月一杯はフリーでダウンロードできるとのこと。 <a rel="nofollow" target="

Masahiro Sakai - 2016-07-07T10:19:52+0000 - 更新日時: 2016-07-07T10:19:52+0000

国際会議SAT2016の予稿集、7月一杯はフリーでダウンロードできるとのこと。 http://rd.springer.com/book/10.1007%2F978-3-319-40970-2 PDFだけじゃなくてepubもあるのね。

19th International Conference on Theory and Applications of Satisfiability Testing (SAT2016)
http://sat2016.labri.fr/

Theory and Applications of Satisfiability Testing – SAT 2016 - Springer

Yoriyuki Yamagata - 2016-07-07T11:50:23+0000 - 更新日時: 2016-07-07T11:55:50+0000

全然関係ないのですが、最近のSATのcomplexityてご存知ですか？もちろん問題はNP完全なのですが、worst caseがexponentialなのかsubexponentialなのかどうかとか。 PとEXPのどこかに≠が入ることは知られているので、subexponentialだとしてもおかしくないかなと。

Masahiro Sakai - 2016-07-10T04:11:45+0000

残念ながらよく知らないです。
SATがsubexponentialでもおかしくはないですが、もしそうだとするとNP⊊EXP が示せたことになって、すごいことなのでは？