Details

Autor(en) / Beteiligte

• Zhao, Xishun
• Büning, Hans Kleine
• Bacchus, Fahiem
• Walsh, Toby

Titel

Model-Equivalent Reductions

Ist Teil von

• 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.