Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich. mehr Informationen...
Lecture notes in computer science, 2005, p.355-370
Ort / Verlag
Berlin, Heidelberg: Springer Berlin Heidelberg
Erscheinungsjahr
2005
Quelle
Alma/SFX Local Collection
Beschreibungen/Notizen
In this paper, the notions of polynomial–time model equivalent reduction and polynomial–space model equivalent reduction are introduced in order to investigate in a subtle way the expressive power of different theories. We compare according to these notions some classes of propositional formulas and quantified Boolean formulas. Our results show that classes of theories with the same complexity might have different representation strength under some conjectures which are widely believed to be true in computation complexity theory.