Strong partial clones and the time complexity of SAT problems
详细信息 查看全文
- 作者：Peter Jonssona ; peter.jonsson@liu.se" class="auth_mail" title="E-mail the corresponding author ; Victor Lagerkvistb ; victor.lagerqvist@tu-dresden.de" class="auth_mail" title="E-mail the corresponding author ; Gustav Nordhc ; gustav.nordh@gmail.com" class="auth_mail" title="E-mail the corresponding author ; Bruno Zanuttinid ; bruno.zanuttini@unicaen.fr" class="auth_mail" title="E-mail the corresponding author
- 关键词：Satisfiability problems ; Computational complexity ; Clone theory ; Universal algebra ; Subexponential time
- 刊名：Journal of Computer and System Sciences
- 出版年：2017
- 出版时间：March 2017
- 年：2017
- 卷：84
- 期：Complete
- 页码：52-78
- 全文大小：864 K
文摘
- •
We investigate the complexity of SAT(⋅) with partial clone theory.
- •
We identify the computationally easiest NP-complete SAT(⋅) problem.
- •
We study the time complexity of this problem and relate it to 1-in-3-SAT.
- •
We relate the easiest SAT(⋅) problem to the exponential-time hypothesis.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |