简介: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.
简介:Givennpropositionalvariables,letKn(i,j),0≤i≤j≤n,betheset(ordisjunction)ofallconjunctionsofiliteralsofwhichexactlyjliteralsarenegative.DunhamandWangconjecturedthatitmayrequireexponentialtimetodecidethateverydisjunctionKn(i,j)isnotvalidbytheresolutionmetho.Thispapergivesaproofoftheconjectureandthenexhibitsanewcounterexampletothefeasibilityoftheresolutionorconsensusmethod.
简介:SometestingresultsonDAWINING-1000,Paragonandworkstationclusteraredescribedinthispaper.Onthehome-madeparallelsystemDAWNING-1000with32computationalprocessors,thepracticalperformanceof1.1777Gflopsand1.58Gflopshasbeenmeasuredinsolvingadenselinearsystemanddoingmatrixmultiplication,respectively.Thescalabilityisalsoinvestigated.Theimportanceofdesigningefficientparallelalgorithmsforevaluatingparallelsystemsisemphasized.