We show that any proof that promise - = p romise - necessitates proving circuit lower bounds that almost yield that = . More accurately, we show that if promise - = p romise - , then for essentially any super-constant function f ( n ) = (1) it holds that NTIM E [ n f ( n ) ] pol y . The conclusion of the foregoing conditional statement cannot be improved (to conclude that pol y ) without \emph{unconditionally} proving that = .
This paper is a direct follow-up to the very recent breakthrough of Murray and Williams (ECCC, 2017), in which they proved a new ``easy witness lemma'' for NTIM E [ o ( 2 n )] . Following their approach, we apply the new lemma within the celebrated proof strategy of Williams (SICOMP, 2013), and derive our result by using a parameter setting that is different than the ones they considered.