On some promise classes in structural complexity theory [Elektronische Ressource] / von Jörg Rothe

On Some Promise Classesin Structural Complexity TheoryDissertationzur Erlangung des akademischen Gradesdoctor rerum naturalium (Dr. rer. nat.)vorgelegt dem Rat derFakultat¨ fur¨ Mathematik und Informatikder Friedrich-Schiller-Universitat¨ Jenavon Diplom-MathematikerJor¨ g Rothegeb. am 1. November 1966 in ErfurtGutachter: Prof. Dr. Gerd WechsungProf. Lane A. HemaspaandraProf. Dr. Uwe Schoning¨Tag des Rigorosums: 5. Oktober 1995¨Tag der offentlichen Verteidigung: 12. 1995To my parentsivAcknowledgmentsProfessor Gerd Wechsung, my advisor, has been the most influential and decisive personregarding my scientific career. He not only nurtured my pleasure in mathematics when I wasan undergraduate student but also introduced me to the joy and challenge of doing research.I very much appreciate his inspiring and enthusiastic way of creating and formalizing ideasand his graceful style of holding lectures as well as his humane warmth, grace, and optimism.I am particularly grateful to him for bringing about my collaboration with Professor LaneHemaspaandra and, in general, for his constant encouragement and support.I am very grateful to Professor Lane Hemaspaandra for his kind guidance, insightfuladvice, and seminal collaboration during my one year stay at the University of Rochesterand ever since.