摘要
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.
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.
基金
This work is supported by the key project fund of China's Ninth Fivesyear Plan and the Science Foundation of Peking University
