The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
Some of the questions posed by Baker, Gill, and Solovay [1] are here answered. The principal result is that there exists a recursive oracle for which the relativized polynomial hierarchy exists through the second level; that is, there is a recursive set B such that Σ2P,B ≠ π2P,B. It follows that Σ2P,B ⊂≠ Σ3P,B.
We employ elementary results from the theory of several complex variables to obtain a quadratic lower bound on the complexity of computing the mean distance between points in the plane. This problem has 2N inputs and a single output and we show that exactly N(N-1)/2 square roots must be computed by any program over +, -, ×, ÷,) √, log and comparisons, even allowing an arbitrary field of constants...
Several polynomial time approximation algorithms for some NP-complete routing problems are presented, and the worst-case ratios of the cost of the obtained route to that of an optimal are determined. A mixed-strategy heuristic with a bound of 9/5 is presented for the Stacker-Crane problem (a modified Traveling Salesman problem). A tour-splitting heuristic is given for k-person variants of the Traveling...
Trie structures are a convenient way of indexing files in which keys are specified by values of attributes. Records correspond to leaves in the trie. Retrieval proceeds by following a path from the root to a leaf, the choice of edges being determined by attribute values. The size of a trie for a file depends on the order in which attributes are tested. We show that determining minimal size tries is...
Motivated by an elementary programming system for formal language generation, we propose a generalized a pushdown acceptor which uses both a checking stack and a pushdown store in original manner. In the analysis of the machine-model parallel rewriting appears to be a fundamental tool for breaking the implicit recursion-structure. Variations of the machine-model (in the sense of Cook) lead to a natural...
A context-free language is said to be simple if it is accepted by a single-state deterministic push-down store acceptor that operates in real-time and accepts by empty store. While the problem remains open of deciding whether or not the language accepted by a deterministic pushdown store acceptor is simple, it is shown that this problem is equivalent to another problem in schemata theory. This question...
Consider n processes operating asynchronously in parallel, each of wich maintains a single "special" variable which can be read (but not written) by the other processes. All coordination between processes is to be accomplished by means of the execution of the primitive operations of a process (1) reading another process's special variable, and (2) setting its own special variable to some...
The Folklore is replete with stories of "secure" protection systems being compromised in a matter of hours. This is quite astounding since one is not likely to claim that a system is secure without some sort of proof to support the claim. In practice, proof is not provided and one reason for this is clear: although the protection primitives are apparently quite simple, they may potentially...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.