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"”.

  1. 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 …

    boise Repository record for Computable Reducibility of Equivalence Relations (opens in a new tab)

  2. 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 …

    wurz-thes Repository record for Multiobjective Traveling Salesman Problems and Redundancy of Complete Sets (opens in a new tab)

  3. 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 …

    cornell Repository record for Measuring the Relative Complexity of Mathematical Constructions and Theorems (opens in a new tab)