direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Es gibt keine deutsche Übersetzung dieser Webseite.

Fixed-Parameter Tractability with SAT Oracles

M.Sc. Ronald de Haan (TU Wien)

Modern SAT solvers have an enormous importance and impact in many practical settings. They are used as efficient back-end to solve many NP-complete problems. However, many computational problems are located at the second level of the Polynomial Hierarchy (PH) or even higher, and hence for these problems polynomial-time transformations to SAT are not possible, unless the hierarchy collapses. Using parameterized complexity, one can in certain cases reduce such problems to SAT with fixed-parameter tractable (fpt) reductions, and therefore efficiently employ SAT solvers to solve problems higher in the PH.

We discuss how this novel tractability notion of fpt-reducibility to SAT can be useful to solve problems that are "beyond NP". We give examples of tractability results for various variants of this notion. Additionally, we present a hardness framework that can be used to give evidence against the existence of fpt-reductions to SAT. Finally, we discuss some examples of problems related to judgment aggregation in the field of computational social choice, whose complexity could be revisited using the new perspective on tractability.

Ronald de Haan
TEL 512

Back to the research colloquium site.

Zusatzinformationen / Extras