Una $\Delta$-tautologia è una tautologia del tipo $H \rightarrow K$ avente un solo interpolante di Craig $J$, a meno di equivalenza logica. Utilizzando misure di complessità relative al problema di trovare tale $J$, mostriamo come si possano ottenere limiti non uniformi di complessità mediante limiti uniformi, e viceversa.
Delta-tautologies, uniform and nonuniform upper bounds in computation theory / D.Mundici. - In: ATTI DELLA ACCADEMIA NAZIONALE DEI LINCEI. RENDICONTI DELLA CLASSE DI SCIENZE FISICHE, MATEMATICHE E NATURALI. - ISSN 0392-7881. - STAMPA. - 75:(1983), pp. 99-101.
Delta-tautologies, uniform and nonuniform upper bounds in computation theory
MUNDICI, DANIELE
1983
Abstract
Una $\Delta$-tautologia è una tautologia del tipo $H \rightarrow K$ avente un solo interpolante di Craig $J$, a meno di equivalenza logica. Utilizzando misure di complessità relative al problema di trovare tale $J$, mostriamo come si possano ottenere limiti non uniformi di complessità mediante limiti uniformi, e viceversa.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
