Relativized isomorphisms of NP-complete sets

In this paper, we present several results about collapsing and non-collapsing degrees ofNP-complete sets. The first, a relativized collapsing result, is interesting because it is the strongest known constructive approximation to a relativization of Berman and Hartmanis' 1977 conjecture that all _m ^P -complete sets forNP arep-isomorphic. In addition, the collapsing result explores new territory in oracle construction, particularly in combining overlapping and apparently incompatible coding and diagonalizing techniques. We also present non-collapsing results, which are notable for their technical simplicity, and which rely on no unproven assumptions such as one-way functions. The basic technique developed in these non-collapsing constructions is surprisingly robust, and can be combined with many different oracle constructions.     

Functions Computable with Nonadaptive Queries to NP

We study FP_|| ^NP , the class of functions that can be computed in polynomial time with nonadaptive queries to an NP oracle. This is motivated by the question of whether it is possible to compute witnesses for NP sets within FP_|| ^NP . The known algorithms for this task all require sequential access to the oracle. On the other hand, there is no evidence known yet that this should not be possible with parallel queries. We define a class of optimization problems based on NP sets, where the optimum is taken over a polynomially bounded range (NPbOpt). We show that if such an optimization problem is based on one of the known NP-complete sets, then it is hard for FP_|| ^NP . Moreover, we characterize FP_|| ^NP as the class of functions that reduces to such optimization functions. We call this property strong hardness. The main question is whether these function classes are complete for FP_|| ^NP . That is, whether it is possible to compute an optimal value for a given optimization problem in FP_|| ^NP . We show that these optimization problems are complete for FP_|| ^NP , if and only if one can compute membership proofs for NP sets in FP_|| ^NP . This indicates that the completeness question is a hard one. Received October 1995, and in final form March 1997.     

Model Checking Abilities of Agents: A Closer Look

Alternating-time temporal logic (atl) is a logic for reasoning about open computational systems and multi-agent systems. It is well known that atl model checking is linear in the size of the model. We point out, however, that the size of an atl model is usually exponential in the number of agents. When the size of models is defined in terms of states and agents rather than transitions, it turns out that the problem is (1) Δ ₃ ^P -complete for concurrent game structures, and (2) Δ ₂ ^P -complete for alternating transition systems. Moreover, for “Positive atl” that allows for negation only on the level of propositions, model checking is (1) Σ ₂ ^P -complete for concurrent game structures, and (2) NP-complete for alternating transition systems. We show a nondeterministic polynomial reduction from checking arbitrary alternating transition systems to checking turn-based transition systems, We also discuss the determinism assumption in alternating transition systems, and show that it can be easily removed. In the second part of the paper, we study the model checking complexity for formulae of atl with imperfect information (atl _ir ). We show that the problem is Δ ₂ ^P -complete in the number of transitions and the length of the formula (thereby closing a gap in previous work of Schobbens in Electron. Notes Theor. Comput. Sci. 85(2), 2004). Then, we take a closer look and use the same fine structure complexity measure as we did for atl with perfect information. We get the surprising result that checking formulae of atl _ir is also Δ ₃ ^P -complete in the general case, and Σ ₂ ^P -complete for “Positive atl _ir ”. Thus, model checking agents’ abilities for both perfect and imperfect information systems belongs to the same complexity class when a finer-grained analysis is used.     

Lattice constants matricial equations for conversion matrices

In this paper we proof a theorem concerning lattice constants and hence three matricial equations for conversion matricesR: if H=Δ^RT we have: i)H ³ =I; ii) H^T Σ H= Σ; iii)(DH) ² =I; where Δ,D, and ε are known when we can enumerate all non-isomorphic graphs withn vertices, we know (for Δ and ε) their edge-number and (for ε) the order of their automorphism group.     

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.     

Machines that Can Output Empty Words

We propose the e-model for leaf languages which complements the known balanced and unbalanced concepts. Inspired by the neutral behavior of rejecting paths of NP machines, we allow transducers to output empty words. The paper explains several advantages of the new model. A central aspect is that it allows us to prove strong gap theorems: For any class that is definable in the e-model, either or . For the existing models, gap theorems, where they exist at all, only identify gaps for the definability by regular languages. We prove gaps for the general case, i.e., for the definability by arbitrary languages. We obtain such general gaps for NP, coNP, 1NP, and co1NP. For the regular case we prove further gap theorems for Σ₂^P, Π₂^P, and Δ₂^P. These are the first gap theorems for Δ₂^P. This work is related to former work by Bovet, Crescenzi, and Silvestri, Vereshchagin, Hertrampf et al., Burtschick and Vollmer, and Borchert et al. An extended abstract of this paper was presented at the 31st International Symposium on Mathematical Foundations of Computer Science (MFCS 2006).S. Travers supported by the Konrad-Adenauer-Stiftung.     

Relativized polynomial hierarchies extending two levels

The existence of relativized polynomial hierarchies extending exactly two levels is shown. More precisely, oraclesX andY are constructed such thatNP(X) ₂ ^{P, X} = ₂ ^{P, X} and ₂ ^{P, Y} ₂ ^{P, Y} = ₂ ^{P, Y} . These results answer a question posed by Baker, Gill, and Solovay ([1]) and generalize their constructions of relativized polynomial hierarchies extending 0 resp. 1 level; i.e.,P(A) = NP(A) resp.P(B) NP(B) = coNP(B) for recursive oraclesA andB.     

Observations on measure and lowness for Δ 2 P

Assuming thatk≥2 and Δ _k ^/P does not have p-measure 0, it is shown that BP · Δ _k ^/P =Δ _k ^/P . This implies that the following conditions hold if Δ ₂ ^P does not have p-measure 0:

Equivalence Problems for Circuits over Sets of Natural Numbers

We investigate the complexity of equivalence problems for {∪,∩,⁻,+,×}-circuits computing sets of natural numbers. These problems were first introduced by Stockmeyer and Meyer (1973). We continue this line of research and give a systematic characterization of the complexity of equivalence problems over sets of natural numbers. Our work shows that equivalence problems capture a wide range of complexity classes like NL, C ₌ L, P,Π₂^P, PSPACE, NEXP, and beyond. McKenzie and Wagner (2003) studied related membership problems for circuits over sets of natural numbers. Our results also have consequences for these membership problems: We provide an improved upper bound for the case of {∪,∩,⁻,+,×}-circuits.     

An oracle builder’s toolkit

We show how to use various notions of genericity as tools in oracle creation. In particular,

1. we give an abstract definition of genericity that encompasses a large collection of different generic notions;

2. we consider a new complexity class AWPP, which contains BQP (quantum polynomial time), and infer several strong collapses relative to -generics;

3. we show that under additional assumptions these collapses also occur relative to Cohen generics;

4. we show that relative to -generics, ULIN∩co-ULINDTIME(n^k) for any k, where ULIN is unambiguous linear time, despite the fact that UP(NP∩co-NP)P relative to these generics;

5. we show that there is an oracle relative to which NP/1∩co-NP/1(NP∩co-NP)/poly; and

6. we use a specialized notion of genericity to create an oracle relative to which

NP^BPPMA.

RelativizedNC

This paper introduces a notion of relativized depth for circuit families and discusses issues regarding uniform families of relativized circuits. This allows us to define a version of relativizedNC and compare it under various oracles with relativizedL, NL, andP. We see thatNC ₁ is properly contained inL if and only if there exists an oracleA such thatNC ₁ ^A is properly contained inL ^A . There is an oracleA where the hierarchy collapses,NC ₁ ^A = NC ^A , and another whereNC ₁ ^A NC ₂ ^A NC ^A P ^A . We then construct anA so that, for anyk, NC ₁ ^A contains a set not inNSPACE ^A (O(n ^k )), suggesting that the notion of relativized space is too weak or that of relativized depth is too strong.     

Some structural properties of SAT

The following four conjectures about structural of SAT are studied in this paper.(1) SAT∈P^SPARSE∩NP;(2)SAT∈SRTDtt;(3)SAT∈Ptt^bAPP;(4)FPtt^SAT=FTlog^SAT.It is proved that some pairs of these conjectures imply P=NP ,for example,if SAT∈P^SPARSE∩NP and SAT∈Ptt^bAPP,or if SAT∈SRTDtt and SAT∩PttbAPP,then P=NP.This improves previous results in literature.     

Does the Polynomial Hierarchy Collapse if Onto Functions are Invertible?

The class TFNP, defined by Megiddo and Papadimitriou, consists of multivalued functions with values that are polynomially verifiable and guaranteed to exist. Do we have evidence that such functions are hard, for example, if TFNP is computable in polynomial-time does this imply the polynomial-time hierarchy collapses? By computing a multivalued function in deterministic polynomial-time we mean on every input producing one of the possible values of the function on that input. We give a relativized negative answer to this question by exhibiting an oracle under which TFNP functions are easy to compute but the polynomial-time hierarchy is infinite. We also show that relative to this same oracle, P≠UP and TFNP^NP functions are not computable in polynomial-time with an NP oracle.     

Derandomizing Arthur-Merlin Games and Approximate Counting Implies Exponential-Size Lower Bounds

We show that if Arthur-Merlin protocols can be derandomized, then there is a language computable in deterministic exponential-time with access to an NP oracle that requires circuits of exponential size. More formally, if every promise problem in prAM, the class of promise problems that have Arthur-Merlin protocols, can be computed by a deterministic polynomial-time algorithm with access to an NP oracle, then there is a language in E^NP that requires circuits of size Ω(2 ⁿ /n). The lower bound in the conclusion of our theorem suffices to construct pseudorandom generators with exponential stretch.     

Convergence Analysis of Batch Gradient Algorithm for Three Classes of Sigma-Pi Neural Networks

Sigma-Pi (Σ-Π) neural networks (SPNNs) are known to provide more powerful mapping capability than traditional feed-forward neural networks. A unified convergence analysis for the batch gradient algorithm for SPNN learning is presented, covering three classes of SPNNs: Σ-Π-Σ, Σ-Σ-Π and Σ-Π-Σ-Π. The monotonicity of the error function in the iteration is also guaranteed.

---

     

On counting and approximation

Summary We introduce a new class of functions, called span functions which count the different output values that occur at the leaves of the computation tree associated with a nondeterministic polynomial time Turing machine transducer. This function class has natural complete problems; it is placed between Valiant's function classes # P and # NP, and contains both Goldberg and Sipser's ranking functions for sets in NP, and Krentel's optimization functions. We show that it is unlikely that the span functions coincide with any of the mentioned function classes. A probabilistic approximation method (using an oracle in NP) is presented to approximate span functions up to any desired degree of accuracy. This approximation method is based on universal hashing and it never underestimates the correct value of the approximated function.The research of this author was supported by the Deutsche Forschungsgemeinschaft, grant No. Scho 302/2The research of this author was done while he was at the EWH Koblenz, with a CIRIT scholarship     

Strong self-reducibility precludes strong immunity

Do self-reducible sets inherently lack immunity from deterministic polynomial time? Though this is unlikely to be true in general, in this paper we prove that sufficiently strong self-reducibility precludes sufficiently strong immunity from deterministic polynomial time. In particular, we prove that NT isnot P balanced immune. However, we prove that NT, a class whose sets have very strong self-reducibility properties, is P bi-immune relative to a generic oracle. Thus, the previous result cannot be relativizably extended to bi-immunity. We also prove that NP and ⊕P are both P balanced immune relative to a random oracle; the former provides the strongest known relativized separation of NP from P.     

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.     

Orthonormal Basis Functions for Continuous-Time Systems and Lp Convergence

In this paper, model sets for linear-time-invariant continuous-time systems that are spanned by fixed pole orthonormal bases are investigated. These bases generalize the well-known Laguerre and two-parameter Kautz cases. It is shown that the obtained model sets are everywhere dense in the Hardy space H ₁(Π) under the same condition as previously derived by the authors for the denseness in the (Π is the open right half plane) Hardy spaces H _p(Π), 1<p<∞. As a further extension, the paper shows how orthonormal model sets, that are everywhere dense in H _p(Π), 1≤p<∞, and which have a prescribed asymptotic order, may be constructed. Finally, it is established that the Fourier series formed by orthonormal basis functions converge in all spaces H _p(Π) and (D is the open unit disk) H _p(D), 1<p<∞. The results in this paper have application in system identification, model reduction, and control system synthesis. Date received: June 16, 1998. Date revised February 4, 1999.     

A relationship between difference hierarchies and relativized polynomial hierarchies

Chang and Kadin have shown that if the difference hierarchy over NP collapses to levelk, then the polynomial hierarchy (PH) is equal to thekth level of the difference hierarchy over ₂ ^p . We simplify their poof and obtain a slightly stronger conclusion: if the difference hierarchy over NP collapses to levelk, then PH collapses to (P _(k–1) ^NP )^NP, the class of sets recognized in polynomial time withk – 1 nonadaptive queries to a set in NP^NP and an unlimited number of queries to a set in NP. We also extend the result to classes other than NP: For any classC that has _m ^p -complete sets and is closed under _conj ^p -and _m ^NP -reductions (alternatively, closed under _disj ^p -and _m ^co-NP -reductions), if the difference hierarchy overC collapses to levelk, then PH ^C = (P _(k–1)–tt ^NP ) ^C . Then we show that the exact counting class C_P is closed under _disj ^p - and _m ^co-NP -reductions. Consequently, if the difference hierarchy over C_P collapses to levelk, then PH^PP(= PH^C_P) is equal to (P _(k–1)–tt ^NP )^PP. In contrast, the difference hierarchy over the closely related class PP is known to collapse.Finally we consider two ways of relativizing the bounded query class P _k–tt ^NP : the restricted relativization P _k–tt ^{NP C} and the full relativization (P _k–tt ^NP ) ^C . IfC is NP-hard, then we show that the two relativizations are different unless PH ^C collapses.Richard Beigel was supported in part by NSF Grants CCR-8808949 and CCR-8958528. Richard Chang was supported in part by NSF Research Grant CCR 88-23053. This work was done while Mitsunori Ogiwara was at the Department of Information Science, Tokyo Institute of Technology, Tokyo, Japan.