Hasso-Plattner-InstitutSDG am HPI
Hasso-Plattner-InstitutDSG am HPI

Enumeration Complexity of Problems in P

Chair for Algorithm Engineering
Hasso Plattner Institute

Office: A-1.7/8
Tel.: +49 331 5509-3917
E-Mail: Stefan.Neubert(at)hpi.de
Links: Homepage

Supervisor: Prof. Dr. Tobias Friedrich
Advisor: Dr. Katrin Casel

In complexity theory, we try to figure out, how fast we can solve a problem. We discuss both how fast an existing algorithm for a problem is as well as whether there are inherent limits to how fast an algorithm can possibly solve a problem. Usually, one analyzes how long it takes an algorithm to solve a given problem instance from receiving the input data until completing computation and producing the output data. In my research I attempt an even more precise analysis: When provided with the input data, how long does it take till the first part of the solution is done? When will the second, third, … part be completed?

The goal of my research is to develop an enumeration complexity theory for problems in P. In particular this theory aims to provide new insights into complexity differences between problems that, under the textbook total-time complexity analysis, are currently undistinguishable.

Currently, we are working on enumerating solutions to scheduling problems.

Last Update: 11-2021