On the Complexity of Determinations

Joseph M. Hellerstein

Classical complexity theory measures the cost of computing a function, but many computational tasks require committing to one valid output among several. We introduce determination…