-tautologies, uniform and non-uniform upper bounds in computation theory
Una -tautologia è una tautologia del tipo avente un solo interpolante di Craig , a meno di equivalenza logica. Utilizzando misure di complessità relative al problema di trovare tale , mostriamo come si possano ottenere limiti non uniformi di complessità mediante limiti uniformi, e viceversa.