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 refining the formal framework for enumeration problems.
