Minimal pairs for P (Q795830)

A general minimal pair theorem is presented. This theorem yields as corollaries many results about minimal pairs in the polynomial-time context obtained previously by various authors. Furthermore, the new counterintuitive result is obtained that there exist ''arbitrarily complex'' minimal pairs. Also, the question whether minimal pairs in NP are ''low'' is investigated.