you're reading...

SACT Seminar: Parameterized Complexity of Problems in the Polynomial Hierarchy

Time: 1:30pm Tuesday, 1st March.

Location: SIT 459

Speaker: Ronald de Haan, TU Wien, Austria

Title: Parameterized Complexity of Problems in the Polynomial Hierarchy

Parameterized complexity provides a theoretical framework that allows for an analysis of the complexity of problems where structure that is present in the input can be taken into account. This provides a way to relativize overly negative hardness results from classical complexity theory. For instance, for many problems that get the classical label “NP-complete”, one can use parameterized complexity to identify efficient algorithms for cases when the input exhibits one of various kinds of structure (these are called fixed-parameter tractable algorithms, or fpt-algorithms). For problems at higher levels of the Polynomial Hierarchy, however, the structure that is required to obtain such fpt-algorithms tends to be very restrictive. Since only few inputs in practical applications show such restrictive structure, fpt-algorithms for these problems are likely to be less useful in practice. Motivated by the impressive performance of SAT solving algorithms (and algorithms for other NP problems), instead of solving problems directly with an fpt-algorithm, one could use fpt-algorithms to encode problem inputs efficiently into an instance of SAT, and subsequently use the SAT algorithm to solve the problem. In this talk, we discuss how to perform a structured parameterized complexity investigation aimed at identifying such fpt-reductions to SAT. We illustrate this by means of various example problems from the domain of artificial intelligence and knowledge representation and reasoning.


No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Enter your email address to subscribe to receive notifications of new announcements by email.

Join 61 other followers

%d bloggers like this: