AF: Small: Measure in Total Function Complexity Classes

This project will develop new tools for investigating the computational complexity of total function problems in theoretical computer science. Traditional computational complexity focuses on decision problems, which have a clear yes or no answer. Total function problems are more complex, requiring the actual construction of a solution.

Examples include cryptographic tasks like integer factoring and economic tasks like finding Nash equilibria. Resource-bounded measure is a tool that has been successful in understanding the computational complexity of decision problems. In this project, we will extend resource-bounded measure to operate in the function problem setting.

The new theory and findings will be promoted to the global theoretical computer science community through a Zoom seminar series. The seminar series will culminate in a workshop at the University of Wyoming in the third year, gathering graduate students and leading computational complexity researchers to discuss and promote the newly developed tools.

Although resource-bounded measure has been effective in studying decision problems and traditional complexity classes, it currently does not address the complexity of function problems. We will introduce a new type of martingales that operates on function values, enabling the development of a new theory of resource-bounded measure in total function classes.

These new martingales will allow for the formulation and analysis of more complex prediction strategies, filling a significant gap in computational complexity theory and extending the application of measure theory more broadly. The project will significantly impact our understanding of pseudorandomness, circuit-size complexity, fine-grained complexity, computational intractability, and the complexity landscape of total function complexity classes.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.