Adaptive versus nonadaptive queries to NP and p-selective sets

We prove that P = NP follows if for some , the class of functions that are computable in polynomial time by nonadaptively accessing an oracle in NP is effectively included in PF^NP[k⌈log n⌉— 1], the class of functions that are computable in polynomial k⌈log n⌉— 1 queries to an oracle in NP.?We draw several observations and relationships between the following two properties of a complexity class : whether there exists a truthtable hard p-selective language for , and whether polynomially-many nonadaptive queries to can be answered by making O(log n)-many adaptive queries to (in symbols, whether ). Among these, we show that if there exists an NP-hard p-selective set under truth-table reductions, then . However, if , then these two properties are equivalent. Received: November 1, 1996.     

Weakly useful sequences

An infinite binary sequence x is defined to be

(i) strongly useful if there is a computable time bound within which every decidable sequence is Turing reducible to x; and

(ii) weakly useful if there is a computable time bound within which all the sequences in a non-measure 0 subset of the set of decidable sequences are Turing reducible to x.

Juedes, Lathrop, and Lutz [Theorectical Computer Science 132 (1994) 37] proved that every weakly useful sequence is strongly deep in the sense of Bennett [The Universal Turing Machine: A Half-Century Survey, 1988, 227] and asked whether there are sequences that are weakly useful but not strongly useful. The present paper answers this question affirmatively. The proof is a direct construction that combines the martingale diagonalization technique of Lutz [SIAM Journal on Computing 24 (1995) 1170] with a new technique, namely, the construction of a sequence that is “computably deep” with respect to an arbitrary, given uniform reducibility. The abundance of such computably deep sequences is also proven and used to show that every weakly useful sequence is computably deep with respect to every uniform reducibility.

Reductions between disjoint NP-Pairs

Disjoint NP-pairs are pairs (A, B) of nonempty, disjoint sets in NP. We prove that all of the following assertions are equivalent: There is a many-one complete disjoint NP-pair; there is a strongly many-one complete disjoint NP-pair; there is a Turing complete disjoint NP-pair such that all reductions are smart reductions; there is a complete disjoint NP-pair for one-to-one, invertible reductions; the class of all disjoint NP-pairs is uniformly enumerable. Let A, B, C, and D be nonempty sets belonging to NP. A smart reduction between the disjoint NP-pairs (A, B) and (C, D) is a Turing reduction with the additional property that if the input belongs to A B, then all queries belong to C D. We prove under the reasonable assumption that UP ∩ co-UP has a P-bi-immune set that there exist disjoint NP-pairs (A, B) and (C, D) such that (A, B) is truth-table reducible to (C, D), but there is no smart reduction between them. This paper contains several additional separations of reductions between disjoint NP-pairs. We exhibit an oracle relative to which DistNP has a truth-table-complete disjoint NP-pair, but has no many-one-complete disjoint NP-pair.     

On sets turing reducible to p-selective sets

We consider sets Turing reducible to p-selective sets under various resource bounds and a restricted number of queries to the oracle. We show that there is a hierarchy among the sets polynomial-time Turing reducible to p-selective sets with respect to the degree of a polynomial bounding the number of adaptive queries used by a reduction. We give a characterization of EXP/poly in terms of exponential-time Turing reducibility to p-selective sets. Finally we show that EXP cannot be reduced to the p-selective sets under 2 ^lin time reductions with at mostn ^k queries for anyfixed k ε N.     

Generalized theorems on relationships among reducibility notions to certain complexity classes

In this paper we give several generalized theorems concerning reducibility notions to certain complexity classes. We study classes that are either (I) closed under NP many-one reductions and polynomial-time conjunctive reductions or (II) closed under coNP many-one reductions and polynomial-time disjunctive reductions. We prove that, for such a classK, (1) reducibility notions of sets toK under polynomial-time constant-round truth-table reducibility, polynomial-time log-Turing reducibility, logspace constant-round truth-table reducibility, logspace log-Turing reducibility, and logspace Turing reducibility are all equivalent and (2) every set that is polynomial-time positive Turing reducible to a set inK is already inK.From these results, we derive some observations on the reducibility notions to C₌P and NP.     

The Difference between Polynomial-Time Many-One and Truth-Table Reducibilities on Distributional Problems

In this paper we separate many-one reducibility from truth-table reducibility for distributional problems in DistNP under the hypothesis that P ≠ NP . As a first example we consider the 3-Satisfiability problem (3SAT) with two different distributions on 3CNF formulas. We show that 3SAT with a version of the standard distribution is truth-table reducible but not many-one reducible to 3SAT with a less redundant distribution unless P = NP . We extend this separation result and define a distributional complexity class C with the following properties: (1) C is a subclass of DistNP, this relation is proper unless P = NP. (2) C contains DistP, but it is not contained in AveP unless DistNP \subseteq AveZPP. (3) C has a ≤ ^p _m -complete set. (4) C has a ≤ ^p _tt -complete set that is not ≤ ^p _m -complete unless P = NP. This shows that under the assumption that P ≠ NP, the two completeness notions differ on some nontrivial subclass of DistNP.     

A Good Oracle Is Hard to Beat

A well-known result of Sacks [24] states that if A is nonrecursive, then the set {B : A ≤ _T B} has measure zero. Thus, from a measure-theoretic perspective, a ``good' (i.e., nonrecursive) oracle is hard to beat in the partial order of Turing degrees. We show that analogous results hold for the standard notions of inductive inference, as well as for the notions of approximate inference. Received January 25, 1997; revised March 10, 1997, June 3, 1997, and June 15, 1997.     

Iterative Methods for Linear Complementarity Problems with Interval Data

A ] and an interval vector [b]. If all A∈[A] are H-matrices with positive diagonal elements, these methods are all convergent to the same interval vector [x ^*]. This interval vector includes the solution x of the linear complementarity problem defined by any fixed A∈[A] and any fixed b∈[b]. If all A∈[A] are M-matrices, then we will show, that [x ^*] is optimal in a precisely defined sense. We also consider modifications of those methods, which under certain assumptions on the starting vector deliver nested sequences converging to [x ^*]. We close our paper with some examples which illustrate our theoretical results. Received October 7, 2002; revised April 15, 2003 Published online: June 23, 2003 RID="*" ID="*" Dedicated to U. Kulisch on the occasion of his 70th birthday. We are grateful to the referee who has given a series of valuable comments.     

Calculating the Galois Group of Y′ = = = AY + + + B,Y′ = = = AY Completely Reducible

We consider a special case of the problem of computing the Galois group of a system of linear ordinary differential equations Y′ = MY, M C (x)^{n × n}. We assume that C is a computable, characteristic-zero, algebraically closed constant field with a factorization algorithm. There exists a decision procedure, due to Compoint and Singer, to compute the group in case the system is completely reducible. Berman and Singer (1999, J. Pure Appl. Algebr., 139, 3–23) address the case in which M = [yjsco5390x.gif M 1 * 0 M 2 ], Y′ = M_iY completely reducible for i = 1, 2. Their article shows how to reduce that case to the case of an inhomogeneous system Y′ = AY + B, A C (x)^{n × n}, B C (x)ⁿ, Y′ = AY completely reducible. Their article further presents a decision procedure to reduce this inhomogeneous case to the case of the associated homogeneous system Y′ = AY. The latter reduction involves using a cyclic-vector algorithm to find an equivalent inhomogeneous scalar equation L(y) = b,L C(x)[ D ], b C (x), then computing a certain set of factorizations of L in C(x)[D ]; this set is very large and difficult to compute in general. In this article, we give a new and more efficient algorithm to reduce the case of a system Y′ = AY + B,Y′ = AY completely reducible, to that of the associated homogeneous systemY′ = AY. The new method’s improved efficiency comes from replacing the large set of factorizations required by the Berman–Singer method with a single block-diagonal decomposition of the coefficient matrix satisfying certain properties.     

Bounded query machines: On NP and PSPACE

It is shown that NP is equal to PSPACE if and only if for every oracle set A, NP(A) is equal to the class NPQUERY(A) of languages accepted by nondeterministic polynomial space-bounded oracle machines that are allowed to query the oracle for A only a polynomial number of times. Further, it is shown that there is an oracle set B such that NPQUERY(B) is not equal to the class PQUERY(B) of languages accepted by deterministic polynomial space-bounded oracle machines that are allowed to query the oracle for B only a polynomial number of times.     

A reducibility concept for problems defined in terms of ordered binary decision diagrams

Reducibility concepts are fundamental in complexity theory. Usually, they are defined as follows: A problem Π is reducible to a problems Σ if Π can be computed using a program or device for Σ as a subroutine. However, this approach has its limitations if restricted computational models are considered. In the case of ordered binary decision diagrams (OBDDs), it allows the use of merely the almost unmodified original program for the subroutine. Here we propose a new reducibility for OBDDs: We say that Π is reducible to Σ if and OBDD for Π can be constructed by applying a sequence of elementary operations to an OBDD for Σ. In contrast to traditional reducibility notions, the newly introduced reduction is able to reflect the real needs of a reducibility concept in the context of OBDD-based complexity classes: it allows the reduction of problems to others which are computable with the same amount of OBDD-resources and it gives a tool to carry over lower and upper bounds. The authors are grateful to DAAD Acciones Integradas, Grant No. 322-ai-e-dr.     

Local Approximability of Max-Min and Min-Max Linear Programs

In a max-min LP, the objective is to maximise ω subject to A x≤1, C x≥ω 1, and x≥0. In a min-max LP, the objective is to minimise ρ subject to A x≤ρ 1, C x≥1, and x≥0. The matrices A and C are nonnegative and sparse: each row a _i of A has at most Δ _I positive elements, and each row c _k of C has at most Δ _K positive elements.     

Controllability for Discrete Systems with a Finite Control Set

In this paper we consider the problem of controllability for a discrete linear control system x _k+1=Ax _k+Bu _k, u _k∈U, where (A,B) is controllable and U is a finite set. We prove the existence of a finite set U ensuring density for the reachable set from the origin under the necessary assumptions that the pair (A,B) is controllable and A has eigenvalues with modulus greater than or equal to 1. In the case of A only invertible we obtain density on compact sets. We also provide uniformity results with respect to the matrix A and the initial condition. In the one-dimensional case the matrix A reduces to a scalar λ and for λ>1 the reachable set R(0,U) from the origin is?

Comparing Nontriviality for E and EXP

A set A is nontrivial for the linear-exponential-time class E=DTIME(2 ^lin ) if for any k≥1 there is a set B _k ∈E such that B _k is (p-m-)reducible to A and B_k ? DTIME(2^k·n)B_{k} \not\in \mathrm{DTIME}(2^{k\cdot n}). I.e., intuitively, A is nontrivial for E if there are arbitrarily complex sets in E which can be reduced to A. Similarly, a set A is nontrivial for the polynomial-exponential-time class EXP=DTIME(2 ^poly ) if for any k≥1 there is a set [^(B)]_k ? EXP\hat{B}_{k} \in \mathrm {EXP} such that [^(B)]_k\hat{B}_{k} is reducible to A and [^(B)]_k ? DTIME(2^nk)\hat{B}_{k} \not\in \mathrm{DTIME}(2^{n^{k}}). We show that these notions are independent, namely, there are sets A ₁ and A ₂ in E such that A ₁ is nontrivial for E but trivial for EXP and A ₂ is nontrivial for EXP but trivial for E. In fact, the latter can be strengthened to show that there is a set A∈E which is weakly EXP-hard in the sense of Lutz (SIAM J. Comput. 24:1170–1189, 11) but E-trivial.     

Computability and Complexity in Self-assembly

This paper explores the impact of geometry on computability and complexity in Winfree’s model of nanoscale self-assembly. We work in the two-dimensional tile assembly model, i.e., in the discrete Euclidean plane ℤ×ℤ. Our first main theorem says that there is a roughly quadratic function f such that a set A⊆ℤ⁺ is computably enumerable if and only if the set X _A ={(f(n),0)∣n∈A}—a simple representation of A as a set of points on the x-axis—self-assembles in Winfree’s sense. In contrast, our second main theorem says that there are decidable sets D⊆ℤ×ℤ that do not self-assemble in Winfree’s sense.     

Properties of the Realization of Inner Functions

 In this paper we investigate fundamental properties of state-space realizations for inner functions. We derive necessary and sufficient conditions for the inner function to have a realization such that the associated C ₀-semigroup is exponentially stable. Furthermore, we give necessary and sufficient conditions on the inner function such that the C ₀-semigroup is a group. Combining these results, we have that the C ₀-semigroup is an exponentially stable C ₀-group if and only if the inner function is the product of a constant of modulus one and a Blaschke product for which the zeros satisfy the Carleson–Newman condition and the zeros lie in a vertical strip bounded away from the imaginary axis. Date received: January 11, 1999. Date revised: May 16, 2002. RID="*" ID="*"This paper was supported by the Volkswagen Stiftung (RiP program at Oberwolfach) and by the Deutsche Forschungsgemeinschaft.     

Reducibility of operation symbols in term rewriting systems and its application to behavioral specifications

In this paper, we propose the notion of reducibility of symbols in term rewriting systems (TRSs). For a given algebraic specification, operation symbols can be classified on the basis of their denotations: the operation symbols for functions and those for constructors. In a model, each term constructed by using only constructors should denote an element, and functions are defined on sets formed by these elements. A term rewriting system provides operational semantics to an algebraic specification. Given a TRS, a term is called reducible if some rewrite rule can be applied to it. An irreducible term can be regarded as an answer in a sense. In this paper, we define the reducibility of operation symbols as follows: an operation symbol is reducible if any term containing the operation symbol is reducible. Non-trivial properties of context-sensitive rewriting, which is a simple restriction of rewriting, can be obtained by restricting the terms on the basis of variable occurrences, its sort, etc. We confirm the usefulness of the reducibility of operation symbols by applying them to behavioral specifications for proving the behavioral coherence property.     

Actions,finite state sets and applications to trees

Let M be a monoid acting on a set X; for any x?X and A?X we put x ^?1 A = {m?M/xm?A}. Call A?X finite state if card {x ^?1 A/x?X} <∞.

The finite state subsets of T _Σvia the action T _Σ × P _Σ→T _Σare the recognizable forests (P _Σis the monoid of all Σ-trees with just one leaf labeled by a variable x).

Next we prove that the recognizability of forests is equivalent to the finiteness of a certain “syntactic” monoid A Mezei's-like theorem for trees is established: the finite state subsets of T _Σ × T_г are exactly the finite unions of sets of sets of the form B × C B?Rec(T _Σ) and C?Rec(T _г) Another characterization of such relations is given using bimorphisms.     

Characterizing polynomial complexity classes by reducibilities

A series of recent results has characterized membership in certain complexity classes in terms of specific types of reductions: a set is in the class if and only if it is reducible to almost every set. We define a new notion of reducibility which characterizes the classes _k ^p ,k>0, of the polynomial-time hierarchy in this way. As an application, we show that the levels of the polynomial-time hierarchy are distinct if and only if uniform witnesses to this separation exist.This research was supported in part by the National Science Foundation under Grant CCR86-11980.     

A theoretical and empirical investigation of multi‐item on‐line auctions

In this paper we explore and analyze the structure of Internet auctions from an analytical and an empirical perspective. Such web‐based auctions are rapidly emerging as a mercantile process of choice in the electronic marketplace. We observe current Internet auctions for one‐time products, such as rapidly aging hardware, and analyze them within the framework of the existing auction theory. While traditional auction theory focuses on single‐item auctions, we observe that a majority of on‐line auctions are multi‐item auctions. A significant contribution of this work is the theoretical derivation of the structure of the winning bids in multi‐item progressive on‐line auctions. Additionally, for comparative purposes, we explore the structural characteristics of alternative multi‐item auction mechanisms proposed in the auction theory. We derive hypotheses based on our analytical results and compare two different types of auction mechanisms. We test the traditional auction theory assumption regarding the homogeneity of bidders and present the first ever empirically derived classification and performance‐comparison of on‐line bidders. We test our hypotheses using real‐world empirical data obtained by tracking a premier web‐based auction site. Statistical analysis of the data indicates that firms may gain by choosing alternative auction mechanisms. We also provide directions for further exploration of this emerging but important dimension of electronic commerce. This revised version was published online in July 2006 with corrections to the Cover Date.