Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 3 of 3 for “"Computable reducibility"”.
-
Computable Reducibility of Equivalence Relations
Computable reducibility of equivalence relations is a tool to compare the complexity of equivalence relations on natural numbers. Its use is important to those doing Borel equivalence relation theory, computability theory, and computable structure theory. In this thesis, we compare many naturally …
-
Multiobjective Traveling Salesman Problems and Redundancy of Complete Sets
… set, then it is called mitotic. For different reducibility notions and complexity classes, we analyze how redundant its complete sets are. Previous research in this field concentrates on polynomial-time computable reducibility notions. The main contribution of this part of the thesis is a …
-
Measuring the Relative Complexity of Mathematical Constructions and Theorems
… and theorems using the frameworks of computable reducibilities and reverse mathematics. First, we study the computational content of various theorems with reverse mathematical strength around Arithmetical Transfinite Recursion ($\mathsf{ATR}_0$) from the point of view of computable …