Some structural properties of SAT
The following four conjectures about structural properties of SAT are studied in this paper. (1) SAT is an element of P-SPARSE boolean AND NP; (2) SAT is an element of SRTDtt; (3) SAT is an element of P-tt(bAPP); (4) FPttSAT = FPlogSAT It is proved that some pairs of these conjectures imply P = NP, for example, if SAT is an element of P-SPARSE boolean AND NP and SAT is an element of P-tt(bAPP), or if SAT is an element of SRTDtt and SAT is an element of P-tt(bAPP), then P = NP. This improves previous results in literature.
sat structural complexity sparse set approximable set truth-table reduction non-adaptive search reducible to decision