论文部分内容阅读
The following four conjectures about structural properties of SAT are studied in this paper. (1) SAT ∈ PSPARSE∩NP; (2) SAT ∈ SRTDtt; (3) SAT ∈ PbttAPP; (4) FPSttAT ＝ FPSATlog. It is proved that some pairs of these conjectures imply P ＝ NP, for example, if SAT ∈ PSPARSE∩NP and SAT ∈ PbttAPP, or if SAT ∈ SRTDtt and SAT ∈ PbttAPP, then P = NP. This improves previous results in literature.