Überarb. Habil.-Schr. Univ. Tübingen, 2006. / Register. Literaturverz.: S. 285-313.

No description available.

This thesis is divided into two parts. In the first part we contribute to a working program initiated by Pudlák (2017) who lists several major complexity theoretic conjectures relevant to proof complexity and asks for oracles that separate pairs of corresponding relativized conjectures. Among these conjectures are: - \(\mathsf{CON}\) and \(\mathsf{SAT}\): coNP (resp., NP) does not contain complete sets that have P-optimal proof systems. - \(\mathsf{CON}^{\mathsf{N}}\): coNP does not contain complete sets that have optimal proof systems. - \(\mathsf{TFNP}\): there do not exist complete total polynomial search problems (also known as total NP search problems). - \(\mathsf{DisjNP}\) and \(\mathsf{DisjCoNP}\): There do not exist complete disjoint NP pairs (coNP pairs). - \(\mathsf{UP}\): UP does not contain complete problems. - \(\mathsf{NP}\cap\mathsf{coNP}\): \(\mathrm{NP}\cap\mathrm{coNP}\) does not contain complete problems. - \(\mathrm{P}\ne\mathrm{NP}\). We construct several of the oracles that Pudlák asks for. In the second part we investigate the computational complexity of balance problems for \(\{-,\cdot\}\)-circuits computing finite sets of natural numbers (note that \(-\) denotes the set difference). These problems naturally build on problems for integer expressions and integer circuits studied by Stockmeyer and Meyer (1973), McKenzie and Wagner (2007), and Glaßer et al. (2010). Our work shows that the balance problem for \(\{-,\cdot\}\)-circuits is undecidable which is the first natural problem for integer circuits or related constraint satisfaction problems that admits only one arithmetic operation and is proven to be undecidable. Starting from this result we precisely characterize the complexity of balance problems for proper subsets of \(\{-,\cdot\}\). These problems turn out to be complete for one of the classes L, NL, and NP. / Diese Arbeit gliedert sich in zwei Teile. Im ersten Teil liefern wir Beiträge zu einem Arbeitsprogramm, das von Pudlák (2017) initiiert wurde, welcher einige bedeutsame komplexitätstheoretische, für das Gebiet der Proof Complexity relevante Vermutungen untersucht und nach Orakeln fragt, die Paare von entsprechenden relativierten Vermutungen separieren. Unter diesen Vermutungen sind: - \(\mathsf{CON}\) und \(\mathsf{SAT}\): coNP (resp., NP) enthält keine vollständigen Probleme, die P-optimale Beweissysteme haben. - \(\mathsf{CON}^{\mathsf{N}}\): coNP enthält keine vollständigen Probleme, die optimale Beweissysteme haben. - \(\mathsf{TFNP}\): Es existieren keine vollständigen Total Polynomial Search Problems (auch bekannt unter dem Namen Total NP Search Problems). - \(\mathsf{DisjNP}\) und \(\mathsf{DisjCoNP}\): Es gibt keine vollständigen disjunkten NP-Paare (coNP-Paare). - \(\mathsf{UP}\): UP enthält keine vollständigen Probleme. - \(\mathsf{NP}\cap\mathsf{coNP}\): \(\mathrm{NP}\cap\mathrm{coNP}\) enthält keine vollständigen Probleme. - \(\mathrm{P}\ne\mathrm{NP}\) Wir konstruieren einige der Orakel, nach denen Pudlák fragt. Im zweiten Teil untersuchen wir die Berechnungskomplexität von Balance Problemen für \(\{-,\cdot\}\)-Schaltkreise, welche endliche Teilmengen natürlicher Zahlen berechnen (es bezeichnet \(-\) die Differenz von Mengen). Diese Probleme bauen in natürlicher Weise auf Probleme für Integer Expressions und Integer Circuits auf, welche von Stockmeyer und Meyer (1973), McKenzie und Wagner (2007) sowie Glaßer et al. (2010) untersucht wurden. Wir beweisen, dass das Balance Problem für \(\{-,\cdot\}\)-Schaltkreise unentscheidbar ist. Dies ist das erste natürliche Problem für Integer Circuits oder verwandte Constraint Satisfaction Probleme, das nur eine arithmetische Operation erlaubt und als unentscheidbar bewiesen worden ist. Von diesem Resultat ausgehend wird die Komplexität von Balance Problemen für echte Teilmengen von \(\{-,\cdot\}\) präzise charakterisiert. Es stellt sich heraus, dass jedes dieser Probleme vollständig für eine der Klassen L, NL und NP ist.

Many applications and protocols on blockchain platforms are reliant on real-world data which exists outside the blockchain, something which is not directly accessible through these platforms. To bridge this gap, blockchain oracles help these applications and protocols by providing them with this data. As different data used by these applications and protocols can result in different outcomes occurring, one way for attackers to attack these applications and protocols is to attack the oracles they rely on. This thesis investigates what types of fundamental attacks are possible on oracles hosted on Ethereum, potential ways to protect against them and how these attacks can be categorized. It also investigates if the different attributes of Solana or Corda provides any protection against these attacks in some way. In order to answer these questions, the different blockchain platforms are researched and investigated, along with different oracles and attacks on oracles. A framework which describes the different states data in a oracle can be in was also created in order to help find attacks. In total, eleven different fundamental attacks on Ethereum oracles were found along with different methods to protect against them. A majority of these attacks were deemed to be able to be done in full capability by both independent and nation-state attackers. Both Solana and Corda were found to provide some inherent protection against some of these attacks. Solana was found to be able to almost fully eliminate one type of attack due to its execution environment. Corda was found to make many of the found attacks harder to execute for an attacker, mainly due to its lack of anonymity. / Många applikationer och protokoll på blockkedje-plattformar är beroende av verklig data som existerar utanför blockkedjan, något som inte är direkt nåbart genom dessa plattformar. I syfte att göra denna data nåbar, så hjälper orakel på blockkedjor dessa applikationer och protokoll genom att tillhandahålla dem denna data. Eftersom dessa applikationer och protokoll kan ha olika utfall beroende på vilken data de använder sig av, så är en metod att attackera dem genom att attackera dem orakel som de använder sig av. Denna avhandling undersöker vilka typer av fundamentala attacker som är möjliga mot orakel som körs på Ethereum, potentiella sätt att skydda mot attackerna samt hur dessa attacker kan kategoriseras. Den undersöker även ifall de olika attributen som finns hos Solana eller Corda ger något skydd mot dessa attacker på något sätt. För att besvara dessa frågor har de olika blockkedjeplattformarna undersökts. Även olika orakel samt attacker mot orakel har undersökts. Ett ramverk som beskriver de olika tillstånden som data i ett orakel kan befinna sig i skapades med syfte att underlätta hittandet av attacker. Totalt så hittades elva olika fundamentala attacker mot orakel som körs på Ethereum tillsammans med tillhörande skyddsmetoder. Majoriteten av dessa attacker bedömdes kunna genomföras i full förmåga av både självständiga angripare samt nationssponsrade angripare. Både Solana och Corda visade sig ge skydd mot vissa av de elva attackerna genom sina attribut. Solana kan genom sin exekveringsmiljö nästan helt eliminera möjligheten av en av attackerna. Corda visade sig göra flera av de olika attackerna svårare att genomföra för angripare, främst på grund av sin avsaknad av anonymitet i plattformen.

This essay explores the divinatory practice of incubation in ancient Egypt during the Graeco-Roman period with a particular focus on the magical and religious significance of the practice. Two main sanctuaries, Abydos and Deir el-Bahari have been investigated with a focus on the gods Bes and Osiris in the former and Amenhotep and Imhotep in the latter. The study has mainly examined surviving epigraphy and the ritual and cultic elements of the sites in relation to physical space as a prerequisite for ritual incubation. In addition, this study has related Greek influences on the practice of incubation in Egypt as a potential source of origin but has also investigated indigenous Egyptian traditions both for questioning the origin of and placing the practice into context. / Denna uppsats undersöker den spådomspraktik så kallad inkubation i Antika Egypten under dess Grekisk-romerska period med ett särskilt fokus på den magiska och religiösa meningen med praktiken. Två primära helgedomar, nämligen Abydos och Deir el-Bahari, har undersökts med ett fokus på gudarna Bes och Osiris i den förra och Amenhotep samt Imhotep i den senare. Studien har främst undersökt kvarlevande epigrafik och den rituella och det kultiska elementet av platserna i relation till fysiskt utrymme som en föregångare för rituell inkubation. Dessutom har denna studie relaterat grekiska influenser på inkubation i Egypten som ett potentiellt ursprung men har även undersökt inhemsk egyptisk tradition både i frågan om dess härkomst och för att ställa praktiken i sin kontext.

Testing is an important step in the software development process in order to increase the reliability of the software. There are a number of different methods available to test software that use different approaches to find errors, all with different requirements and possible results. In this thesis we have performed a series of tests on our own mobile application developed for the Android platform. The thesis starts with a theory section in which most of the important terms for software testing are described. Afterwards our own application and test cases are presented. The results of our tests along with our experiences are reviewed and compared to existing studies and literature in the field of testing. The test cases have helped us find a number of faults in our source code that we had not found before. We have discovered that automated testing for Android is a field where there are a lot of good tools, although these are not often used in practice. We believe the app development process could be improved greatly by regularly putting the software through automated testing systems.

Von Haus aus sind Sibyllinische Orakel eine griechisch-römische Literaturgattung, eine Sammlung von Orakelsprüchen in griechischen Hexametern, die nicht erhalten ist. Die uns überlieferten Sibyllinischen Orakel sind jüdischen, christlichen und teilweise paganen Ursprungs. Die insgesamt 14 Bücher sind in den Jahren 150 vor bis 300 nach Christus entstanden. Bis zu ihrer Wiederentdeckung im Vatikan waren die Sibyllinischen Orakel nur durch Zitate der Kirchenväter bekannt. Buch 3 ist laut Mehrheit der Forscher das älteste der Sammlung und entstand im zweiten vorchristlichen Jahrhundert in Ägypten. Die Arbeit stellt diesen Konsens in Frage. Sie konzentriert sich dabei auf die Vorstellung der Beherrschung des Raumes im dritten Sibyllinischen Orakel. Dabei geht es einerseits um die rein geographische Vorstellung der Welt, die der Sibylle zugrunde liegt und andererseits um die politisch-theologische Vorstellung der Abfolge von Weltreichen, die diese Welt nacheinander beherrschen und schlussendlich von der Herrschaft Gottes abgelöst werden. Das Thema Gottesherrschaft nimmt in den jüdischen Pseudepigraphen eine relativ marginale Rolle ein. Dies könnte sicherlich damit zusammenhängen, dass die Diasporaschriften nicht unmittelbar unter dem Einfluss der sogenannten Antiochenischen Verfolgung und den Makkabäeraufständen standen, anders als z.B. das Danielbuch. In den Texten aus der Diaspora findet sich das Thema Gottesherrschaft sogar nur im dritten Sibyllinischen Orakel und in der Weisheit Salomos. Besonderes Gewicht hat die Gottesherrschaft schließlich in den Schriften des Neuen Testament. Ich hoffe mit meiner Arbeit einen wichtigen Beitrag zur Genese der Vorstellung der Gottesherrschaft im Neuen Testament zu leisten. Der endzeitliche Zustand, den die Sibylle für die Umsetzung der göttlichen Herrschaft auf Erden prophezeit, kann mit dem Begriff Utopie beschrieben werden. / Originally, the Sibylline Oracles were a Graeco-Roman literary genre, namely a collection of oracles composed in Greek hexamters which have not come down to us. The Sibylline Books that we have today are of Jewish and Christian origin and stem from a time when the genre was adapted first by Jews and then Christians. The altogether 14 books have developed between 150 BCE and 300 CE and for the longest time were only known through quotations in the church fathers such as Eusebius and Lactantius. According to the majority of scholars, Book III is the oldest of the Sibylline corpus and developed in the 2nd century BCE in Egypt. This thesis reconsiders the established consensus using old and new evidence alike. It focuses on the image of dominion of space in the Third Sibyl. On the one hand, space is looked at as the geographical image of the world as the Sibyl has access to, on the other, space is looked at as the political-theological image of succession of empires that rule the world consecutively until eventually they are superseded by the dominion of God. The dominion of God only play a minor role in Jewish pseudepigraphy. This could be related to the fact that the writings of the Diaspora were not immediately affected by the so-called Antiochene persecution and the Maccabean revolt unlike, for instance, the Book of Daniel. In the writings of the Diaspora the topic only occurs in the Third Sibyl and in the Wisdom of Solomon. It becomes particularly important in the New Testament. With this thesis I hope to provide an important contribution to the genesis of the image of the dominion of God in the New Testament. The eschatological age that the Sibyl prophecies for the establishment of the divine dominion on earth can be described using the term utopia.

In dieser Arbeit beschäftigen wir uns mit dem Wasserstein Baryzentrumproblem diskreter Wahrscheinlichkeitsmaße sowie mit dem population Wasserstein Baryzentrumproblem gegeben von a Fréchet Mittelwerts von der rechnerischen und statistischen Seiten. Der statistische Fokus liegt auf der Schätzung der Stichprobengröße von Maßen zur Berechnung einer Annäherung des Fréchet Mittelwerts (Baryzentrum) der Wahrscheinlichkeitsmaße mit einer bestimmten Genauigkeit. Für empirische Risikominimierung (ERM) wird auch die Frage der Regularisierung untersucht zusammen mit dem Vorschlag einer neuen Regularisierung, die zu den besseren Komplexitätsgrenzen im Vergleich zur quadratischen Regularisierung beiträgt. Der Rechenfokus liegt auf der Entwicklung von dezentralen Algorithmen zurBerechnung von Wasserstein Baryzentrum: duale Algorithmen und Sattelpunktalgorithmen. Die Motivation für duale Optimierungsmethoden ist geschlossene Formen für die duale Formulierung von entropie-regulierten Wasserstein Distanz und ihren Derivaten, während, die primale Formulierung nur in einigen Fällen einen Ausdruck in geschlossener Form hat, z.B. für Gaußsches Maß. Außerdem kann das duale Orakel, das den Gradienten der dualen Darstellung für die entropie-regulierte Wasserstein Distanz zurückgibt, zu einem günstigeren Preis berechnet werden als das primale Orakel, das den Gradienten der (entropie-regulierten) Wasserstein Distanz zurückgibt. Die Anzahl der dualen Orakel rufe ist in diesem Fall ebenfalls weniger, nämlich die Quadratwurzel der Anzahl der primalen Orakelrufe. Im Gegensatz zum primalen Zielfunktion, hat das duale Zielfunktion Lipschitz-stetig Gradient aufgrund der starken Konvexität regulierter Wasserstein Distanz. Außerdem untersuchen wir die Sattelpunktformulierung des (nicht regulierten) Wasserstein Baryzentrum, die zum Bilinearsattelpunktproblem führt. Dieser Ansatz ermöglicht es uns auch, optimale Komplexitätsgrenzen zu erhalten, und kann einfach in einer dezentralen Weise präsentiert werden. / In this thesis, we consider the Wasserstein barycenter problem of discrete probability measures as well as the population Wasserstein barycenter problem given by a Fréchet mean from computational and statistical sides. The statistical focus is estimating the sample size of measures needed to calculate an approximation of a Fréchet mean (barycenter) of probability distributions with a given precision. For empirical risk minimization approaches, the question of the regularization is also studied along with proposing a new regularization which contributes to the better complexity bounds in comparison with the quadratic regularization. The computational focus is developing decentralized algorithms for calculating Wasserstein barycenters: dual algorithms and saddle point algorithms. The motivation for dual approaches is closed-forms for the dual formulation of entropy-regularized Wasserstein distances and their derivatives, whereas the primal formulation has a closed-form expression only in some cases, e.g., for Gaussian measures.Moreover, the dual oracle returning the gradient of the dual representation forentropy-regularized Wasserstein distance can be computed for a cheaper price in comparison with the primal oracle returning the gradient of the (entropy-regularized) Wasserstein distance. The number of dual oracle calls in this case will be also less, i.e., the square root of the number of primal oracle calls. Furthermore, in contrast to the primal objective, the dual objective has Lipschitz continuous gradient due to the strong convexity of regularized Wasserstein distances. Moreover, we study saddle-point formulation of the non-regularized Wasserstein barycenter problem which leads to the bilinear saddle-point problem. This approach also allows us to get optimal complexity bounds and it can be easily presented in a decentralized setup.