摘要
ThefollowingfourconjecturesaboutstructuralofSATarestudiedinthispaper.(1)SAT∈P^SPARSE∩NP;(2)SAT∈SRTDtt;(3)SAT∈Ptt^bAPP;(4)FPtt^SAT=FTlog^SAT.ItisprovedthatsomepairsoftheseconjecturesimplyP=NP,forexample,ifSAT∈P^SPARSE∩NPandSAT∈Ptt^bAPP,orifSAT∈SRTDttandSAT∩PttbAPP,thenP=NP.Thisimprovespreviousresultsinliterature.
出版日期
2000年05月15日(中国期刊网平台首次上网日期,不代表论文的发表时间)