you're reading...

SACT Seminar: On the Parameterized Complexity of Belief Revision

Time: 12:00 noon Tuesday, 11th October 2016.

Location: SIT 459

Speaker: Stefan Rümmele, University of Sydney

Title: On the Parameterized Complexity of Belief Revision

Belief revision is a core formalism of Artificial Intelligence aiming for a formal way of adapting one’s beliefs in the light of new information. Parameterized complexity is a well recognized vehicle for understanding the multitude of complexity AI problems typically exhibit. However, the prominent problem of belief revision has not undergone a systematic investigation in this direction yet. This is somewhat surprising, since by its very nature of involving a knowledge base and a revision formula, this problem provides a perfect playground for investigating novel parameters. Among our results on the parameterized complexity of revision is thus a versatile fpt algorithm which is based on the parameter of the number of atoms shared by the knowledge base and the revision formula. Towards identifying the frontier between parameterized tractability and intractability, we also give hardness results for classes such as co-W[1], para-Θ_2^P, and FPT^NP[f(k)].

This talk is based on joint work with Andreas Pfandler, Johannes Peter Wallner, and Stefan Woltran.


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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

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

Join 75 other followers

%d bloggers like this: