Faster algorithms and lower bounds for non-monotonic reasoning

NP-hard problems frequently occur in many real-world situations due to their rich modeling power.

Even though only superpolynomial algorithms are currently known, there is still a large practical incentive to find faster algorithms, and significant improvements over brute force search can in general be achieved.

In this project we will investigate superpolynomial algorithms for non-monotonic reasoning problems, with a particular focus on propositional abduction.

Despite seeing many real-world applications, the precise exponential time complexity of abduction is currently a blind spot, and no improved algorithms are known for the NP-hard cases.

We will issue a systematic attack on the complexity of abduction, and other forms of non-monotonic reasoning, by constructing faster algorithms and simultaneously investigate how close to optimal our algorithms are by proving new lower bounds under the exponential-time hypothesis.

To study the complexity in a systematic way we use the constraint based framework employing the algebraic approach based on partial polymorphisms.

To the best of our knowledge we are the first to launch a systematic attack on the exponential time complexity of a problem complete for the second level of the polynomial hierarchy. We will hereby advance tools for exponential time complexity analysis of NP-complete problems to problems beyond NP. The project is to run for four years and fund a PhD student and the applicants´ time for supervision and research.