510 Mathematik
Refine
Year of publication
Document Type
- Preprint (18)
- Article (12)
- Report (12)
- Doctoral Thesis (6)
- Conference Proceeding (4)
- Part of a Book (1)
- Diploma Thesis (1)
Has Fulltext
- yes (54)
Is part of the Bibliography
- no (54)
Keywords
- Kongress (6)
- Kryptologie (5)
- Online-Publikation (4)
- LLL-reduction (3)
- Commitment Scheme (2)
- Knapsack problem (2)
- Lattice basis reduction (2)
- Oblivious Transfer (2)
- San Jose (2)
- Shortest lattice vector problem (2)
Institute
- Informatik (54) (remove)
In this paper, we study the limit of compactness which is a graph index originally introduced for measuring structural characteristics of hypermedia. Applying compactness to large scale small-world graphs (Mehler, 2008) observed its limit behaviour to be equal 1. The striking question concerning this finding was whether this limit behaviour resulted from the specifics of small-world graphs or was simply an artefact. In this paper, we determine the necessary and sufficient conditions for any sequence of connected graphs resulting in a limit value of CB = 1 which can be generalized with some consideration for the case of disconnected graph classes (Theorem 3). This result can be applied to many well-known classes of connected graphs. Here, we illustrate it by considering four examples. In fact, our proof-theoretical approach allows for quickly obtaining the limit value of compactness for many graph classes sparing computational costs.
Die Gotik ist eine Kunstepoche des Mittelalters, die eine große Anzahl beeindruckender Bauten hervorgebracht hat. Hierbei sind besonders die monumentalen Sakralbauten dieser Zeit mit ihren eindrucksvollen Fenstern hervorzuheben. Rosetten gehören zu den größten Fenstern in gotischen Kathedralen. Sie sind kreisförmige Fenster, die vor allem durch ihre komplexe Aufbauweise auffallen. Das Grundbauelement der Rosetten ist das sog. Maßwerk - ein Steinwerk das als dekoratives Muster für Fenster und Wände in gotischen Bauten eingesetzt wird. Charakteristisch für diese Muster sind sich wiederholende, verschieden große geometrische Formen, was an die Eigenschaft der Selbstähnlichkeit bei Fraktalen erinnert.
Die manuelle Modellierung gotischer Fenster ist auf Grund deren komplexen Aufbaus sehr aufwendig. Eine prozedurale Generierung hingegen automatisiert den Modellierungsprozess weitgehend und verringert damit den Zeit- und Modellierungsaufwand per Hand.
In der vorliegenden Arbeit wurde eine prozedurale Methode beschrieben, die die aufwendige manuelle Modellierung der Rosetten bzw. des Maßwerks zum größten Teil ersetzt. Diese Methode basiert auf der Analyse der fraktalen Struktur des Maßwerks und nutzt dabei dessen Selbstähnlichkeit aus, um Rosetten automatisch zu generieren. Mit der in dieser Arbeit entwickelten Implementierung ist es mögliche, eine große Vielfalt gotischer Rosetten zu beschreiben und mit Hilfe der 3D-Grafik-Engine OGRE graphisch darzustellen.
The behaviour of electronic circuits is influenced by ageing effects. Modelling the behaviour of circuits is a standard approach for the design of faster, smaller, more reliable and more robust systems. In this thesis, we propose a formalization of robustness that is derived from a failure model, which is based purely on the behavioural specification of a system. For a given specification, simulation can reveal if a system does not comply with a specification, and thus provide a failure model. Ageing usually works against the specified properties, and ageing models can be incorporated to quantify the impact on specification violations, failures and robustness. We study ageing effects in the context of analogue circuits. Here, models must factor in infinitely many circuit states. Ageing effects have a cause and an impact that require models. On both these ends, the circuit state is highly relevant, an must be factored in. For example, static empirical models for ageing effects are not valid in many cases, because the assumed operating states do not agree with the circuit simulation results. This thesis identifies essential properties of ageing effects and we argue that they need to be taken into account for modelling the interrelation of cause and impact. These properties include frequency dependence, monotonicity, memory and relaxation mechanisms as well as control by arbitrary shaped stress levels. Starting from decay processes, we define a class of ageing models that fits these requirements well while remaining arithmetically accessible by means of a simple structure.
Modeling ageing effects in semiconductor circuits becomes more relevant with higher integration and smaller structure sizes. With respect to miniaturization, digital systems are ahead of analogue systems, and similarly ageing models predominantly focus on digital applications. In the digital domain, the signal levels are either on or off or switching in between. Given an ageing model as a physical effect bound to signal levels, ageing models for components and whole systems can be inferred by means of average operation modes and cycle counts. Functional and faithful ageing effect models for analogue components often require a more fine-grained characterization for physical processes. Here, signal levels can take arbitrary values, to begin with. Such fine-grained, physically inspired ageing models do not scale for larger applications and are hard to simulate in reasonable time. To close the gap between physical processes and system level ageing simulation, we propose a data based modelling strategy, according to which measurement data is turned into ageing models for analogue applications. Ageing data is a set of pairs of stress patterns and the corresponding parameter deviations. Assuming additional properties, such as monotonicity or frequency independence, learning algorithm can find a complete model that is consistent with the data set. These ageing effect models decompose into a controlling stress level, an ageing process, and a parameter that depends on the state of this process. Using this representation, we are able to embed a wide range of ageing effects into behavioural models for circuit components. Based on the developed modelling techniques, we introduce a novel model for the BTI effect, an ageing effect that permits relaxation. In the following, a transistor level ageing model for BTI that targets analogue circuits is proposed. Similarly, we demonstrate how ageing data from analogue transistor level circuit models lift to purely behavioural block models. With this, we are the first to present a data based hierarchical ageing modeling scheme. An ageing simulator for circuits or system level models computes long term transients, solutions of a differential equation. Long term transients are often close to quasi-periodic, in some sense repetitive. If the evaluation of ageing models under quasi-periodic conditions can be done efficiently, long term simulation becomes practical. We describe an adaptive two-time simulation algorithm that basically skips periods during simulation, advancing faster on a second time axis. The bottleneck of two-time simulation is the extrapolation through skipped frames. This involves both the evaluation of the ageing models and the consistency of the boundary conditions. We propose a simulator that computes long term transients exploiting the structure of the proposed ageing models. These models permit extrapolation of the ageing state by means of a locally equivalent stress, a sort of average stress level. This level can be computed efficiently and also gives rise to a dynamic step control mechanism. Ageing simulation has a wide range of applications. This thesis vastly improves the applicability of ageing simulation for analogue circuits in terms of modelling and efficiency. An ageing effect model that is a part of a circuit component model accounts for parametric drift that is directly related to the operation mode. For example asymmetric load on a comparator or power-stage may lead to offset drift, which is not an empiric effect. Monitor circuits can report such effects during operation, when they become significant. Simulating the behaviour of these monitors is important during their development. Ageing effects can be compensated using redundant parts, and annealing can revert broken components to functional. We show that such mechanisms can be simulated in place using our models and algorithms. The aim of automatized circuit synthesis is to create a circuit that implements a specification for a certain use case. Ageing simulation can identify candidates that are more reliable. Efficient ageing simulation allows to factor in various operation modes and helps refining the selection. Using long term ageing simulation, we have analysed the fitness of a set of synthesized operational amplifiers with similar properties concerning various use cases. This procedure enables the selection of the most ageing resilient implementation automatically.
This thesis contributes to the field of machine learning with a specific focus on the methods for learning relations between the inputs. Learning relationships between images is the most common primitive in vision. There are many vision tasks in which relationships across images play an important role. Some of them are motion estimation, activity recognition, stereo vision, multi-view geometry and visual odometry. Many of such tasks mainly depend on motion and disparity cues, which are inferred based on the relations across multiple image pairs. The approaches presented in this thesis mainly deal with, but are not limited to, learning of the representations for motion and depth. This thesis by articles consists of five articles which present relational feature learning models along with their applications in computer vision. In the first article, we present an approach for encoding motion in videos. To this end, we show that the detection of spatial transformations can be viewed as detection of coincidence or synchrony between the given sequence of frames and a sequence of features which are related by the transformation we wish to detect. Learning to detect synchrony is possible by introducing "multiplicative interactions'' into the hidden units of single layered sparse coding models.
We show that the learned motion representations employed for the task of activity recognition achieve competitive performance on multiple benchmarks. Stereo vision is an important challenge in computer vision and useful for many applications in that field. In the second article, we extend the energy based learning models, which were previously used for motion encoding, to the context of depth perception. Given the common architecture of the models for encoding motion and depth, we show that it is possible to define a single model for learning a unified representation for both the cues. Our experimental results show that learning a combined representation for depth and motion makes it possible to achieve state-of-the-art performance at the task of 3-D activity analysis, and to perform better than the existing hand-engineered 3-D motion features. Autoencoder is a popular unsupervised learning method for learning efficient encoding for a given set of data samples. Typically, regularized autoencoders which are used to learn over-complete and sparse representations for the input data, were shown to fail on intrinsically high dimensional data like videos. In the third article, we investigate the reason for such a behavior. It can be observed that the regularized autoencoders typically learn negative hidden unit biases. We show that the learning of negative biases is the result of hidden units being responsible for both the sparsity and the representation of the input data. It is shown that, as a result, the behavior of the model resembles clustering methods which would require exponentially large number of features to model intrinsically high dimensional data. Based on this understanding, we propose a new activation function which decouples the roles of hidden layer and uses linear encoding. This allows to learn representations on data with very high intrinsic dimensionality. We also show that gating connections in the bi-linear models and the single layer models from articles one and two of this thesis can be thought of as a way to attain a linear encoding scheme which allows them to learn good representations on videos. Visual odometry is the task of inferring egomotion of a moving object from visual information such as images and videos. It can primarily be used for the task of localization and has many applications in the fields of robotics and navigation. The work in article four was motivated by the idea of using deep learning techniques, which are successful methods for many vision tasks, for visual odometry. The visual odometry task mainly requires inference of motion and depth information from visual input which can then be mapped to velocity and change in direction. We use relational feature models presented in the articles one and two for inferring a combined motion and depth representation from stereo video sequences. The combined representation is then mapped to discrete velocity and change in direction labels using convolutional neural networks. Our approach is an end-to-end deep learning-based architecture which uses a single type of computational model and learning rule. Preliminary results show that the architecture is capable of learning the mapping from input video to egomotion. Activity recognition is a challenging computer vision task with many real world applications. It is well know that it is a hard task to use computer vision research for real-time applications. In the fifth article of this thesis, we present a real-time activity recognition system based on deep learning based methods. Our approach uses energy based relational feature learning models for the computation of local motion features directly from videos. A bag-of-words over the local motion features is used for the analysis of activity in a given video sequence. We implement this system on a distributed computational platform and demonstrate its performance on the iCub robot. Using GPUs we demonstrate real time performance which makes the deployment of activity recognition systems in real world scenarios possible.
Mathematical modeling of Arabidopsis thaliana with focus on network decomposition and reduction
(2014)
Systems biology has become an important research field during the last decade. It focusses on the understanding of the systems which emit the measured data. An important part of this research field is the network analysis, investigating biological networks. An essential point of the inspection of these network models is their validation, i.e., the successful comparison of predicted properties to measured data. Here especially Petri nets have shown their usefulness as modeling technique, coming with sound analysis methods and an intuitive representation of biological network data.
A very important tool for network validation is the analysis of the Transition-invariants (TI), which represent possible steady-state pathways, and the investigation of the liveness property. The computational complexity of the determination of both, TI and liveness property, often hamper their investigation.
To investigate this issue, a metabolic network model is created. It describes the core metabolism of Arabidopsis thaliana, and it is solely based on data from the literature. The model is too complex to determine the TI and the liveness property.
Several strategies are followed to enable an analysis and validation of the network. A network decomposition is utilized in two different ways: manually, motivated by idea to preserve the integrity of biological pathways, and automatically, motivated by the idea to minimize the number of crossing edges. As a decomposition may not be preserving important properties like the coveredness, a network reduction approach is suggested, which is mathematically proven to conserve these important properties. To deal with the large amount of data coming from the TI analysis, new organizational structures are proposed. The liveness property is investigated by reducing the complexity of the calculation method and adapting it to biological networks.
The results obtained by these approaches suggest a valid network model. In conclusion, the proposed approaches and strategies can be used in combination to allow the validation and analysis of highly complex biological networks.
Driven by rapid technological advancements, the amount of data that is created, captured, communicated, and stored worldwide has grown exponentially over the past decades. Along with this development it has become critical for many disciplines of science and business to being able to gather and analyze large amounts of data. The sheer volume of the data often exceeds the capabilities of classical storage systems, with the result that current large-scale storage systems are highly distributed and are comprised of a high number of individual storage components. As with any other electronic device, the reliability of storage hardware is governed by certain probability distributions, which in turn are influenced by the physical processes utilized to store the information. The traditional way to deal with the inherent unreliability of combined storage systems is to replicate the data several times. Another popular approach to achieve failure tolerance is to calculate the block-wise parity in one or more dimensions. With better understanding of the different failure modes of storage components, it has become evident that sophisticated high-level error detection and correction techniques are indispensable for the ever-growing distributed systems. The utilization of powerful cyclic error-correcting codes, however, comes with a high computational penalty, since the required operations over finite fields do not map very well onto current commodity processors. This thesis introduces a versatile coding scheme with fully adjustable fault-tolerance that is tailored specifically to modern processor architectures. To reduce stress on the memory subsystem the conventional table-based algorithm for multiplication over finite fields has been replaced with a polynomial version. This arithmetically intense algorithm is better suited to the wide SIMD units of the currently available general purpose processors, but also displays significant benefits when used with modern many-core accelerator devices (for instance the popular general purpose graphics processing units). A CPU implementation using SSE and a GPU version using CUDA are presented. The performance of the multiplication depends on the distribution of the polynomial coefficients in the finite field elements. This property has been used to create suitable matrices that generate a linear systematic erasure-correcting code which shows a significantly increased multiplication performance for the relevant matrix elements. Several approaches to obtain the optimized generator matrices are elaborated and their implications are discussed. A Monte-Carlo-based construction method allows it to influence the specific shape of the generator matrices and thus to adapt them to special storage and archiving workloads. Extensive benchmarks on CPU and GPU demonstrate the superior performance and the future application scenarios of this novel erasure-resilient coding scheme.
Das Ziel dieser Arbeit ist es, eine authentische Verdeckung eingebetteter virtueller 3D-Objekte in augmentierten Bilderwelten bei einer geringen Anzahl an Fotos innerhalb der Bilderwelt zu erreichen. Für die Verdeckung von realen und virtuellen Anteilen einer Augmented Reality-Szene sind Tiefeninformationen notwendig. Diese stammen üblicherweise aus einer 3D-Rekonstruktion, für deren Erstellung sehr viele Eingangsbilder notwendig sind. Im Gegensatz dazu wurde in dieser Arbeit ein System entwickelt, das eine vollständige 3D-Rekonstruktion umgeht. Dieses beruht auf einem direkten bildbasierten Rendering-Ansatz, welcher auch mit unvollständigen Tiefeninformationen eine hohe Bildqualität in Bezug auf eine authentische Verdeckung erreicht. Daraus erschließen sich neue Anwendungsgebiete, wie z.B. die automatisierte Visualisierung von 3D-Planungsdaten und 3D-Produktpräsentationen in Bildern bzw. Bilderwelten, da in diesen Bereichen oftmals nicht genügend große Bildmengen vorhanden sind. Gerade für diese Anwendungsgebiete sind authentische Verdeckungen für die Nutzerakzeptanz der Augmentierung wichtig. Unter authentischer Verdeckung wird die entsprechend der menschlichen Wahrnehmung visuell korrekte Überlagerung zwischen virtuellen Objekten und einzelnen Bildanteilen eines oder mehrerer Fotos verstanden. Das Ergebnis wird in Form einer Bilderwelt (eine bildbasierte 3D-Welt, die die Fotos entsprechend der Bildinhalte räumlich anordnet) präsentiert, die mit virtuellen Objekten erweitert wurde. Folglich ordnet sich diese Arbeit in das Fachgebiet der Augmented Reality ein. Im Rahmen dieser Arbeit wurde ein Verfahren für die bildbasierte Darstellung mit authentischen Verdeckungen auf der Basis von unvollständigen Tiefeninformationen sowie unterschiedliche Verfahren für die notwendige Berechnung der Tiefeninformationen entwickelt und gegenübergestellt. Das Sliced-Image-Rendering-Verfahren rendert mithilfe unvollständiger Tiefeninformationen ein Bild ohne 3D-Geometrie als dreidimensionale Darstellung und realisiert auf diese Weise eine authentische Verdeckung. Das Berechnen der dafür notwendigen Tiefeninformationen eines 2D-Bildes stellt eine gesonderte Herausforderung dar, da die Bilderwelt nur wenige und unvollständige 3D-Informationen der abgebildeten Szene bereitstellt. Folglich kann eine qualitativ hochwertige 3D-Rekonstruktion nicht durchgeführt werden. Die Fragestellung ist daher, wie einzelne Tiefeninformationen berechnet und diese anschließend größeren Bildbereichen zugeordnet werden können. Für diese Tiefenzuordnung wurden im Rahmen der vorliegenden Arbeit drei verschiedene Verfahren konzipiert, die sich in Bezug auf genutzte Daten und deren Verarbeitung unterscheiden. Das Segment-Depth-Matching-Verfahren ordnet Segmenten eines Bildes mithilfe der 3D-Szeneninformationen der Bilderwelt eine Tiefe zu. Hierfür werden Segmentbilder vorausgesetzt. Als Ergebnis liegt für jedes Foto eine Depth-Map vor. Um eine Tiefenzuordnung auch ohne eine vorangehende Segmentierung zu ermöglichen, wurde das Key-Point-Depth-Matching-Verfahren entwickelt. Bei diesem Verfahren werden die 3D-Szeneninformationen der Bilderwelt auf die Bildebene als kreisförmige Sprites projiziert. Die Distanz zur Kamera wird dabei als Tiefenwert für das Sprite verwendet. Alle projizierten Sprites einer Kamera ergeben die Depth-Map. Beide Verfahren liefern Flächen mit Tiefeninformationen, aber keine pixelgenauen Depth-Maps. Um pixelgenaue Depth-Maps zu erzeugen, wurde das Geometry-Depth-Matching-Verfahren entwickelt. Bei diesem Verfahren wird eine Szenengeometrie des abgebildeten Szenenausschnittes erzeugt und dadurch eine pixelgenaue Depth-Map erstellt. Hierfür wird ein semiautomatischer Skizzierungsschritt vorausgesetzt. Die erzeugte Szenengeometrie stellt keine vollständige 3D-Rekonstruktion der Bilderweltenszene dar, da nur ein Szenenausschnitt aus Sicht einer Kamera rekonstruiert wird. Anhand einer technischen Umsetzung erfolgte eine Validierung der konzeptionellen Verfahren. Die daraus resultierenden Ergebnisse wurden anhand verschiedener Bilderweltenszenen mit unterschiedlichen Eigenschaften (Außen- und Innenraumszenen, detailreich und -arm, unterschiedliche Bildmengen) evaluiert. Die Evaluierung des Sliced-Image-Renderings zeigt, dass mithilfe unvollständiger Tiefeninformationen der entwickelten Depth-Matching-Verfahren und unter Einhaltung der gestellten Anforderungen (wenig Eingabefotos, kleine Szenen, keine 3D-Rekonstruktion) eine authentische Verdeckung eingebetteter virtueller 3D-Objekte in Bilderwelten realisiert werden kann. Mithilfe des entwickelten Systems können bildbasierte Anwendungen auch mit kleinen Fotomengen Augmentierungen mit hoher Bildqualität in Bezug auf eine authentische Verdeckung realisieren.
Bayessche Methoden zur Schätzung von Stammbäumen mit Verzweigungszeitpunkten aus molekularen Daten
(2009)
Ein großes Ziel der Evolutionsbiologie ist es, die Stammesgeschichte der Arten zu rekonstruieren. Historisch verwendeten Systematiker hierfür morphologische und anatomische Merkmale. Mit dem stetigen Zuwachs an verfügbaren Sequenzdaten werden heute verstärkt Methoden entwickelt und eingesetzt, welche die Rekonstruktion auf Basis von molekularen Daten ermöglichen. Im Fokus der aktuellen Forschung steht die Anwendung und Weiterentwicklung Bayesscher Methoden. Diese Methoden besitzen große Popularität, da sie in Verbindung mit Markov-Ketten-Monte-Carlo-Verfahren eingesetzt werden können, um einen Stammbaum zu vorgegebenen Spezies zu schätzen und dessen Variabilität zu bestimmen. Im Rahmen dieser Dissertation wurde die erweiterbare Software TreeTime entwickelt. TreeTime bietet Schnittstellen für die Einbindung von molekularen Evolutions- und Ratenänderungsmodellen und stellt neu entwickelte Methoden bereit, um Stammbäume mit Verzweigungszeitpunkten zu rekonstruieren. In TreeTime werden die molekularen Daten und die zeitlichen Informationen, wie z.B. Fossilfunde, in einem Bayes-Verfahren simultan berücksichtigt, um die Zeitpunkte der Artaufspaltungen genauer zu datieren. Für die Anwendung Bayesscher Methoden in der Rekonstruktion von Stammbäumen wird ein stochastisches Modell benötigt, das die Evolution der molekularen Sequenzen entlang den Kanten eines Stammbaums beschreibt. Der Mutationsprozess der Sequenzen wird durch ein molekulares Evolutionsmodell definiert. Die Verwendung der klassischen molekularen Evolutionsmodelle impliziert die Annahme einer konstanten Evolutionsgeschwindigkeit der Sequenzen im Stammbaum. Diese Annahme wird als Hypothese der molekularen Uhr bezeichnet und bildet die Grundlage zum Schätzen der Verzweigungszeiten des Stammbaums. Der Verzweigungszeitpunkt, an dem sich zwei Spezies im Stammbaum aufspalten, spiegelt sich in der Ähnlichkeit der zugehörigen molekularen Sequenzen. Je älter dieser Verzweigungszeitpunkt ist, desto größer ist die Anzahl der unterschiedlichen Positionen in den Sequenzen. Häufig ist jedoch die Annahme der molekularen Uhr verletzt, so dass in gewissen Teilbereichen eines Stammbaums eine erhöhte Evolutionsgeschwindigkeit nachweisbar ist. Falls die Verletzung konstanter Evolutionsgeschwindigkeiten nicht ausgeschlossen werden kann, sollten schwankende Mutationsraten in der Modellierung explizit berücksichtigt werden. Hierfür wurden verschiedene Ratenänderungsmodelle vorgeschlagen. Bisher sind nur wenige dieser Ratenänderungsmodelle in Softwarepaketen verfügbar und ihre Eigenschaften sind nicht ausreichend erforscht. Das Ziel dieser Arbeit ist die Entwicklung und Bereitstellung von Bayesschen Modellen und Methoden zum Schätzen von Stammbäumen mit Verzweigungszeitpunkten. Die Methoden sollten auch bei unterschiedlichen Evolutionsgeschwindigkeiten im Stammbaum anwendbar sein. Vorgestellt wird ein neues Ratenänderungsmodell, eine neue Möglichkeit der Angabe von flexiblen Beschränkungen für die Topologie des Stammbaums sowie die Nutzung dieser Beschränkungen für die zeitliche Kalibrierung. Das neue Raten Änderungsmodell sowie die topologischen und zeitlichen Beschränkungen werden in einen modularen Softwareentwurf eingebettet. Durch den erweiterbaren Entwurf können bestehende und zukünftige molekulare Evolutionsmodelle und Ratenänderungsmodelle in die Software eingebunden und verwendet werden. Die vorgestellten Modelle und Methoden werden gemäß dem Softwareentwurf in das neu entwickelte Programm TreeTime aufgenommen und effzient implementiert. Zusätzlich werden bereits vorhandene Modelle programmiert und eingebunden, die nicht in anderen Softwarepaketen verfügbar sind. Des Weiteren wird eine neue Methode entwickelt und angewendet, um die Passgenauigkeit eines Modells für die Apriori-Verteilung auf der Menge der Baumtopologien zu beurteilen. Diese Methode wird zur Auswahl geeigneter Modelle benutzt, indem eine Auswertung der beobachteten Baumtopologien der Datenbank TreeBASE durchgeführt wird. Anschließend wird die Software TreeTime in einer Simulationsstudie eingesetzt, um die Eigenschaften der implementierten Ratenänderungsmodelle zu vergleichen. Die Software wird für die Rekonstruktion des Stammbaums zu 38 Spezies aus der Familie der Eidechsen (Lacertidae) verwendet. Da die zugehörigen molekularen Daten von der Hypothese der molekularen Uhr abweichen, werden unterschiedliche Ratenänderungsmodelle bei der Rekonstruktion verwendet und abschließend bewertet. ........
Considered are the classes QL (quasilinear) and NQL (nondet quasllmear) of all those problems that can be solved by deterministic (nondetermlnlsttc, respectively) Turmg machines in time O(n(log n) ~) for some k Effloent algorithms have time bounds of th~s type, it is argued. Many of the "exhausUve search" type problems such as satlsflablhty and colorabdlty are complete in NQL with respect to reductions that take O(n(log n) k) steps This lmphes that QL = NQL iff satisfiabdlty is m QL CR CATEGORIES: 5.25