First-order spectra with one binary predicate
A Durand, S Ranaivoson - Theoretical Computer Science, 1996 - Elsevier
The spectrum, Sp (ϑ), of a sentence ϑ is the set of cardinalities of finite structures which
satisfy ϑ. We prove that any set of integers which is in≻ Func1∞, ie in the class of spectra of …
satisfy ϑ. We prove that any set of integers which is in≻ Func1∞, ie in the class of spectra of …
Separating classes in the exponential-time hierarchy from classes in PH
SE Mocas - Theoretical Computer Science, 1996 - Elsevier
We are interested in separating classes in the exponential-time hierarchy, EXPH, from
classes in the polynomial-time hierarchy, PH. In this paper we show that, for any fixed …
classes in the polynomial-time hierarchy, PH. In this paper we show that, for any fixed …
[PS][PS] Caract erisations Logiques des Probl emes NP: Robustesse et Normalisation
G Gottlob - 1996 - pageperso.lis-lab.fr
La th eorie de la complexit e algorithmique se propose de donner un sens a la notion de di
cult e de r esolution des probl emes combinatoires. Apr es avoir formalis e de plusieurs mani …
cult e de r esolution des probl emes combinatoires. Apr es avoir formalis e de plusieurs mani …