On the oracle complexity of factoring integers

The problem of factoring integers in polynomial time with the help of an infinitely powerful oracle who answers arbitrary questions with yes or no is considered. The goal is to minimize the number of oracle questions. LetN be a given compositen-bit integer to be factored, wheren = log₂ N. The trivial method of asking for the bits of the smallest prime factor ofN requiresn/2 questions in the worst case. A non-trivial algorithm of Rivest and Shamir requires onlyn/3 questions for the special case whereN is the product of twon/2-bit primes. In this paper, a polynomial-time oracle factoring algorithm for general integers is presented which, for any >0, asks at most n oracle questions for sufficiently largeN, thus solving an open problem posed by Rivest and Shamir. Based on a plausible conjecture related to Lenstra's conjecture on the running time of the elliptic curve factoring algorithm, it is shown that the algorithm fails with probability at mostN ^–/2 for all sufficiently largeN.     

On relativizations with restricted number of accesses to the oracle set

Conflicting relativizations, also known as Baker-Gill-Solovay phenomena, are common place in complexity theory. However, Book, Long, and Selman (SIAM J. Comput.,13 (1984), 461–487) have shown thatP(A) = NP _B (A) for all oraclesA if and only ifP = NP, whereNP _B (A) denotes the class of languages accepted by nondeterministic machines which possess only a polynomial number of query strings in the computation tree. It is shown in this paper that any superpolynomial bound on the number of queries already yields the BGS phenomenon. Similar results hold for theNP = co-NP andNPC = NP questions. A second objective of this paper is to point out a technique of Hartmanis with which to achieve oracle constructions by using the Kolmogorov complexity. This relatively new technique seems to be adequate for obtaining separation results for complexity classes which are not enumerable.     

On languages accepted by space-bounded oracle machines

Characterizations of classes of languages accepted by space-bounded oracle machines are developed. These characterizations are given in terms of the regular sets, certain information about the oracle set, and certain algebraic closure operations.This research was supported in part by the National Science Foundation under Grant MCS77-11360     

On problems for which no oracle can help

It is shown that for some languages no oracle (or only oracles with exponential density—depending on the way in which the space complexity in oracle computations is measured) can help to decrease their time-space complexity. This result is shown to be to some extent independent of the machine model used (single-tape, multitape, or multihead Turing machines, RAMs, etc.)Further, a new complexity measure reflecting the amount of information provided by an oracle for language recognition is introduced. The tradeoff of this measure and time-space complexity is discussed.     

Log space machines with multiple oracle tapes

As an alternative to previously studied models for space-bounded relative computation, an oracle Turing machine with a space bound on its worktape and an arbitrary number of oracle tapes is considered. Basic properties of the resulting reducibilities are examined.     

On the application of boundary conditions to time dependent computations for quasi one-dimensional fluid flows

A study is made of the influence of boundary and initial conditions on time-dependent finite-difference solutions of quasi-one-dimensional duct flows. Several questions are addressed: (1) Under what conditions will a time-dependent solution converge to a steady-state supersonic flow, (2) Under what conditions will it converge to subsonic flow and (3) What conditions are necessary to insure a particular unique solution for subsonic flows. The results provide an orientation, or way of thinking, about the role of such conditions in time-dependent solutions of steady-state flows. The results also show that supersonic solutions are readily obtained by holding only pressure and temperature fixed at the duct inlet, and allowing velocity to float. However, subsonic solutions require pressure, temperature and velocity to be fixed at both the duct inlet and exit. If no conditions are held fixed at the exit, the results always converge to the supersonic solution, even if the fixed inlet mass flow is less than critical. In such a case, the program appears to generate additional mass flow between the inlet and throat, sufficient to choke the flow. These results also have some impact on two- and three-dimensional time-dependent solutions where subsonic flow is present on some or all portions of the flow boundaries.     

On reliability in finite element computations

Direct computation of engineering data from finite element solutions with reasonable guarantee of reliability is discussed with reference to practical engineering problem solving. The discussion focuses on a model problem for which experimental and numerical data are available.     

Optimized FFT computations on heterogeneous platforms with application to the Poisson equation

We develop optimized multi-dimensional FFT implementations on CPU–GPU heterogeneous platforms for the case when the input is too large to fit on the GPU global memory, and use the resulting techniques to develop a fast Poisson solver. The solver involves memory bound computations for which the large 3D data may have to be transferred over the PCIe bus several times during the computation. We develop a new strategy to decompose and allocate the computation between the GPU and the CPU such that the 3D data is transferred only once to the device memory, and the executions of the GPU kernels are almost completely overlapped with the PCI data transfer. We were able to achieve significantly better performance than what has been reported in previous related work, including over 145 GFLOPS for the three periodic boundary conditions (single precision version), and over 105 GFLOPS for the two periodic, one Neumann boundary conditions (single precision version). The effective bidirectional PCIe bus bandwidth achieved is 9–10 GB/s, which is close to the best possible on our platform. For all the cases tested, the single 3D data PCIe transfer time, which constitutes a lower bound on what is possible on our platform, takes almost 70% of the total execution time of the Poisson solver.     

On multiple spline approximations for Bayesian computations

Probabilistic reasoning typically suffers from the explosive amount of information it must maintain. There are a variety of methods available for curbing this explosion. However, in doing so, it is important to avoid oversimplifying the given domain through injudicious use of assumptions such as independence. Multiple splining is an approach for compressing and approximating the probabilistic information. Instead of positing additional independence conditions, it attempts to identify patterns in the information. While the data explosion is multiplicative in nature, O(n ₁ n ₂⋯n _k), multiple splines reduces it to an additive one, O(n ₁ + n ₂ + ⋯n _k). We consider how these splines can be found and used. Since splines exploit patterns in the data, we can also use them to help in filling in missing data. As it turns out, our splining method is quite general and may be applied to other domains besides probabilistic reasoning which can benefit from data compression. This revised version was published online in June 2006 with corrections to the Cover Date.     

On numerical computations in mixed boundary problems

A technique of solving mixed boundary value problems is formulated. The problem is essentially reduced to solving a set of linear algebraic equations, which can be solved efficiently on a computer. The technique is illustrated by two examples. The first deals with the electrostatic potential distribution on a partially grounded annulus. The other concerns with a contact of hollow cylinder, bonded inside to a rigid core.     

Programs with restoration of computations

In this article, the notion of a program with restoration of computations is introduced, i.e., such a program that makes it possible to renew interrupted computations from any intermediate value obtained before an interruption of its operation. As is shown, any operator specified by a regular scheme of algorithmic algebra can be computed by a program with this property. Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 173–181, January–February, 2000.     

On the complexity of simulating space-bounded quantum computations

This paper studies the space-complexity of predicting the long-term behavior of a class of stochastic processes based on evolutions and measurements of quantum mechanical systems. These processes generalize a wide range of both quantum and classical space-bounded computations, including unbounded error computations given by machines having algebraic number transition amplitudes or probabilities. It is proved that any space s quantum stochastic process from this class can be simulated probabilistically with unbounded error in space O(s), and therefore deterministically in space O(s²).     

Structural properties of oracle classes

Denote by the class of oracles relative to which (collapsing oracles), and by the class of oracles relative to which (separating oracles). We present structural results on and . Using a diagonalization argument, we show that neither nor is closed under disjoint union, also known as join. We show that this implies that neither nor is closed under union, intersection, or symmetric difference. Consequently , the first level of the extended low hierarchy, is not closed under join.     

A high-performance application data environment for large-scale scientific computations

Effective high-level data management is becoming an important issue with more and more scientific applications manipulating huge amounts of secondary-storage and tertiary-storage data using parallel processors. A major problem facing the current solutions to this data management problem is that these solutions either require a deep understanding of specific data storage architectures and file layouts to obtain the best performance (as in high-performance storage management systems and parallel file systems), or they sacrifice significant performance in exchange for ease-of-use and portability (as in traditional database management systems). We discuss the design, implementation, and evaluation of a novel application development environment for scientific computations. This environment includes a number of components that make it easy for the programmers to code and run their applications without much programming effort and, at the same time, to harness the available computational and storage power on parallel architectures.     

Real-time computations with restricted nondeterminism

By restricting the number of nondeterministic moves permitted during a real-time Turing machine computation, an infinite hierarchy can be exhibited between the real-time definable languages of Rosenberg and the quasi-real-time languages of Book and Greibach.     

Stability of controllers with on-line computations

The dynamical systems theory developed by Zufiria [1], Zufiria and Guttalu [2, 3], and Guttalu and Zufiria [4] is applied to the stability analysis of control systems in which the feedback control law requires in real time the solution of a set of nonlinear algebraic equations. Since a small sampling period is assumed, the stability and performance of the controlled process can be studied with a continuous-time formulation. A singularly perturbed system is used to model both the dynamics of the system being controlled and a numerical iterative algorithm required to compute the control law. An updating control procedure has been proposed based on the iterative nature of the control algorithm. The results obtained by Zufiria [1] regarding the behavior of a dynamical system that models the numerical algorithms lead to a considerable simplification in the analysis. For the case of a control problem involving inverse kinematics, the numerical algorithm that solves for inverse kinematics can be considered as an observer (or an estimator) of the state-space variables. The study provides an estimate of the required speed of computations to preserve the stability of the controller.Recommended by E .P. Ryan