[For the entire collection see Zbl 0538.00003.]
The author connects the P\(=NP\) problem with the complexity of interpolants of tautological implications by proving that one of the following three conditions holds. (The proof takes the form that the first condition is proved from the assumption of falsity of the last two.)
(i) TAUT \((=the\) set of tautologies) is accepted in deterministic polynomial time (viz. \(P=NP).\)
(ii) TAUT is not accepted in nondeterministic polynomial time (viz. NP\(\neq Co-NP).\)
(iii) Let \(\Sigma\) be the alphabet for sentential calculus, \(\Sigma^*\) be the set of words over \(\Sigma\), and let \(\Phi\) : \(\Sigma^*\times \Sigma^*\to \Sigma^*\). If \(\Phi\) is computable in deterministic polynomial time, then for some tautology \(B\to C\), \(\Phi\) (B,C) cannot be an interpolant for \(B\to C\). (Intractability of the interpolants.)
He also shows that an analogous result holds for any class of functions that include all the polynomials and is closed under composition and sum. The method used is necessarily very computation theoretic (besides the evaluation of the truth values of sentential formulas). The author closes the paper with a survey of the results about complexity of the interpolants in the sentential as well as in the predicate calculi.