期刊文献+
共找到1篇文章
< 1 >
每页显示 20 50 100
Some Structural Properties of SAT
1
作者 刘田 《Journal of Computer Science & Technology》 SCIE EI CSCD 2000年第5期439-444,共6页
The following four conjectures about structural properties of SAT are studied in this paper. (1) SAT ∈ PSPARSEnNP; (2) SAT ∈ SRTDtt; (3) SAT ∈ PttbAPP; (4) FPttSAT = FPlogSAT. It is proved that some pairs of these ... The following four conjectures about structural properties of SAT are studied in this paper. (1) SAT ∈ PSPARSEnNP; (2) SAT ∈ SRTDtt; (3) SAT ∈ PttbAPP; (4) FPttSAT = FPlogSAT. It is proved that some pairs of these conjectures imply P = NP, for example, if SAT E pSPARsEnNP and SAT 6 PttbAPP, or if SAT E SRTDtt and SAT E PttbAPP, then P = NP. This improves previous results in literature. 展开更多
关键词 structural complexity SAT sparse set approximable set truthtable reduction non-adaptive search reducible to decision.
原文传递
上一页 1 下一页 到第
使用帮助 返回顶部