Narrow Results

Recently, boolean hierarchies over NP and over RP (denoted BH and RBH respectively) have been introduced in complexity theory. They have proved particularly useful in carefully classifying natural problems which are not finely classified using more standard time and space complexity classes. In this paper we are particularly interested in the structural properties of these hierarchies and in relationships among various boolean hierarchies.

Establishing the most significant relationships between BH, RBH, and other complexity classes would imply solving some of the major open problems in complexity theory. To date the only significant relations known are: , and RBH⊆BH. Essentially nothing is known about the fine structure of BH or of RBH.

In [5] an oracle X is constructed for which both BH^x and RBH^x have an infinite number of proper levels. Further each level of RBH is properly contained in the corresponding level of BH, and RBH is properly contained in PP. In this paper we further explore these constructions. We prove that some of these separations are “strong” separations. That is, they can be witnessed by sets that cannot be “approximated” by sets in the smaller class: the separating sets are immune to sets from the smaller class.

Specifically, we prove that the separations between RBH, BPP, PP and each level of BH, can be witnessed by immune sets.

China's Imitation Generic Drugs See Less Profit.

Pharmaceutical Firms Vie for China's Cephalosporin Market.

China to Hold Investment Conference in Frankfurt.

Korean Adults Suffer Deteriorating Mental Health.

Singapore Sets up Young Investigators Award to Boost Biomedical Research.

Singapore Turns to Supercomputers to Process Life Science Data.

Review Panel Calls for Overhaul to Singapore's Medical Education System.

Neuroscience Symposium in Singapore.

International Firms Invest in Taiwan's Biotech Market.

Thailand Funds Six Genome Projects.

Thailand to Hold Pharmaceutical Conference.

The Oracle relational database management system, with object-oriented extensions and numerous application-driven enhancements, plays a critical role worldwide in managing the exploding volumes of bioinformatics data. There are many features of the Oracle product which support the bioinformatics community directly already and there are several features which could be exploited more thoroughly by users, service vendors, and Oracle itself to extend that level of support. This paper will present an overview of Oracle features which support storage of bioinformatics data and will discuss extensibility features which give the product room to grow. Some attention will be given to Oracle's own efforts to use that extensibility to exploit emerging standardization of many of the complex data and computation requirements of the life sciences.

The development of relational databases has significantly improved the performance of storage, search, and retrieval functions and has made it possible for applications that perform real-time data acquisition and analysis to interact with these types of databases. The purpose of this research was to develop a user interface for interaction between a data acquisition and analysis application and a relational database using the Oracle9i system. The overall system was designed to have an indexing capability that threads into the data acquisition and analysis programs. Tables were designed and relations within the database for indexing the files and information contained within the files were established. The system provides retrieval capabilities over a broad range of media, including analog, event, and video data types. The system's ability to interact with a data capturing program at the time of the experiment to create both multimedia files as well as the meta-data entries in the relational database avoids manual entries in the database and ensures data integrity and completeness for further interaction with the data by analysis applications.

People always need more information than they have. They can get some of this information by themselves but a good deal of information remains inaccessible. This situation, which always existed in human civilization, brought forth Oracles. The idea of an Oracle reflected interactions between systems, such as people and states, with less information and systems with more indispensable information. In the 20^th century, it was proved that some information is intrinsically inaccessible and then the concept of an Oracle naturally came to computer science becoming popular in the realm of algorithms and computations. At first, Turing machines with an Oracle were introduced and studied. Later inductive Turing machines with Oracles, limit Turing machines with Oracles and evolutionary Turing machines with Oracles were established and explored. Here we create a theoretical background for the concept of an Oracle. In the first part of this work, we contemplate Oracles in human culture. In the second part, we contemplate Oracles in computer science and mathematics. In the third part, the variety of Oracles is analyzed and classified. In the fourth part, we develop a mathematical theory of Oracles, where the concepts of an Oracle and its brands are formalized and studied in the mathematical framework.

Grover’s quantum search algorithm is a template for doing quantum search in unstructured search spaces. The details of the oracle in Grover’s algorithm is abstracted for the purpose of analyzing the bound on the number of queries the algorithm must make in order to find the target element of the search space. In order for Grover’s quantum search algorithm to be usable in a specific unstructured search problem, one must provide details on the inner workings of the oracle.

Specifically, we present a high-level and basic design of the oracle using the quantum computing model specific to the exact string matching problem. We describe our design using the quantum circuit model of computing and show that the gate complexity of the circuit is linear with respect to the product of the length of the pattern and the size of the alphabet. We have suggested a quantum memory structure for storage and retrieval of the input text. The quantum circuit we presented requires scratch qubits linear to the product of the length of the pattern and the size of the alphabet to reduce the size of the scratch register without exponential increase in the count of elementary gates required for the computation.