Return to search

Towards a Theory of Recursive Function Complexity: Sigma Matrices and Inverse Complexity Measures

This paper develops a data structure based on preimage sets of functions on a finite set. This structure, called the sigma matrix, is shown to be particularly well-suited for exploring the structural characteristics of recursive functions relevant to investigations of complexity. The matrix is easy to compute by hand, defined for any finite function, reflects intrinsic properties of its generating function, and the map taking functions to sigma matrices admits a simple polynomial-time algorithm . Finally, we develop a flexible measure of preimage complexity using the aforementioned matrix. This measure naturally partitions all functions on a finite set by characteristics inherent in each function's preimage structure.

Identiferoai:union.ndltd.org:uno.edu/oai:scholarworks.uno.edu:td-3212
Date18 December 2015
CreatorsFournier, Bradford M
PublisherScholarWorks@UNO
Source SetsUniversity of New Orleans
Detected LanguageEnglish
Typetext
Formatapplication/pdf
SourceUniversity of New Orleans Theses and Dissertations
Rightshttp://creativecommons.org/licenses/by/4.0/

Page generated in 0.0017 seconds