Tautologies with a unique Craig interpolant, uniform vs. nonuniform complexity,

If S⊆{0,1};* and S′ = {0,1}*\sbS are both recognized within a certain nondeterministic time bound T then, in not much more time, one can write down tautologies An→A′n with unique interpolants In that define S∩{0,1}n; hence, if one can rapidly find unique interpolants, then one can recognize S within deterministic time Tp for some fixed p\s>0. In general, complexity measures for the problem of finding unique interpolants in sentential logic yield new relations between circuit depth and nondeterministic Turing time, as well as between proof length and the complexity of decision procedures of logical theories.