P-selective sets,tally languages,and the behavior of polynomial time reducibilities onNP

The notion ofp-selective sets, and tally languages, are used to study polynomial time reducibilities onNP. P-selectivity has the property that a setA belongs to the classP if and only if both _m ^p A andA isp-selective. We prove that for every tally language set inNP there exists a polynomial time equivalent set inNP that isp-selective. From this result it follows that if NEXT DEXT, then polynomial time Turing and many-one reducibilities differ onNP. This research was supported in part by the National Science Foundation under grant MCS 77-23493     

Non-determinism and weak constraints in Datalog

This paper introduces a simple and powerful extension of stratified DATALOG which permits to express various DB-complexity classes. The new language, called DATALOG^¬s,c,p , extends DATALOG with stratified negation, a non-deterministic construct, calledchoice, and a weak form of constraints, calledpreference rules, that is, constraints that should be respected but, if they cannot be eventually enforced, they only invalidate the portions of the program which they are concerned with. Although DATALOG with stratified negation is not able to express all polynomial time queries,²⁰⁾ the introduction of the non-deterministic constructchoice permits to express, exactly, the ‘deterministic fragment’ of the class of DB-queriesP, under the non-deterministic semantics,NP, under the possible semantics, and coNP, under the certain semantics. The introduction of preference rules, further increases the expressive power of the language, and permits to express the complexity classes Σ ₂ ^p , under the possibility semantics, and Π ₂ ^p , under the certainty semantics.     

On the Power of DNA-Computing

Adleman used biological manipulations with DNA strings to solve some instances of the Directed Hamiltonian Path Problem. Lipton showed how to extend this idea to solve any NP problem. We prove that exactly the problems in P^NP=Δ^p₂can be solved in polynomial time using Lipton's model. Various modifications of Lipton's model, based on other DNA manipulations, are investigated systematically, and it is proved that their computational power in polynomial time can be characterized by one of the complexity classes P,Δ^p₂, orΔ^p₃.     

On a Refined Analysis of Some Problems in Interval Arithmetic Using Real Number Complexity Theory

We study some problems in interval arithmetic treated in Kreinovich et al. [13]. First, we consider the best linear approximation of a quadratic interval function. Whereas this problem (as decision problem) is known to be NP-hard in the Turing model, we analyze its complexity in the real number model and the analogous class NP . Our results substantiate that most likely it does not any longer capture the difficulty of NP in such a real number setting. More precisely, we give upper complexity bounds for the approximation problem for interval functions by locating it in (a real analogue of). This result allows several conclusions: the problem is not (any more) NP -hard under so called weak polynomial time reductions and likely not to be NP -hard under (full) polynomial time reductions; for fixed dimension the problem is polynomial time solvable; this extends the results in Koshelev et al. [12] and answers a question left open in [13].We also study several versions of interval linear systems and show similar results as for the approximation problem.Our methods combine structural complexity theory with issues from semi-infinite optimization theory.     

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.     

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.     

Subcomplete generalizations of graph isomorphism

We present eight group-theoretic problems in NP one of which is a reformulation of graph isomorphism. We give technical evidence that none of the problems is NP-complete, and give polynomial time reductions among the problems. There is a good possibility that seven of these problems are harder than graph isomorphism (relative to polynomial time reduction), so that they might be examples of natural problems of intermediate difficulty, situated properly between the class of NP-complete problems and the class P of problems decidable in deterministic polynomial time. Because of strong structural similarity, two of the apparently harder problems can be interpreted as generalized isomorphism and generalized automorphism, respectively. Whether these problems ultimately prove to be harder than graph isomorphism seems to depend, in part, on the open problem whether every permutation group of degree n arises as the automorphism group of a combinatorial structure of size polynomial in n. Finally, we give an O(n² · k) algorithm for constructing the centralizer of a permutation group of degree n presented by a generating set of k permutations. Note that we may assume that k is O(n · log n), without loss of generality. This problem is a special case of one of the harder group-theoretic problems. From the method of constructing the centralizer, we recover results about the group-theoretic structure of the centralizer. Furthermore, applying our algorithm for intersecting with a normalizing permutation group, we show how to find the center of a permutation group of degree n in O(n⁶) steps, having constructed the centralizer of the group first.     

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.     

Lower bounds for polynomial evaluation and interpolation problems

We show that there is a set of pointsp ₁,p ₂,...,p _n such that any arithmetic circuit of depthd for polynomial evaluation (or interpolation) at these points has size $$\Omega \left( {\frac{{n\log n}}{{\log (2 + d/\log n}}} \right).$$ Moreover, for circuits of sub-logarithmic depthd, we obtain a lower bound of Ω(dn ^1+1/d ) on its size.     

A novel and quick SVM-based multi-class classifier

Use different real positive numbers p_i to represent all kinds of pattern categories, after mapping the inputted patterns into a special feature space by a non-linear mapping, a linear relation between the mapped patterns and numbers p_i is assumed, whose bias and coefficients are undetermined, and the hyper-plane corresponding to zero output of the linear relation is looked as the base hyper-plane. To determine the pending parameters, an objective function is founded aiming to minimize the difference between the outputs of the patterns belonging to a same type and the corresponding p_i, and to maximize the distance between any two different hyper-planes corresponding to different pattern types. The objective function is same to that of support vector regression in form, so the coefficients and bias of the linear relation are calculated by some known methods such as SVM^light approach. Simultaneously, three methods are also given to determine p_i, the best one is to determine them in training process, which has relatively high accuracy. Experiment results of the IRIS data set show that, the accuracy of this method is better than those of many SVM-based multi-class classifiers, and close to that of DAGSVM (decision-directed acyclic graph SVM), emphatically, the recognition speed is the highest.     

A statistical analysis of the numerical condition of multiple roots of polynomials

Componentwise and normwise condition numbers of an m-tuple root x₀ of a polynomial p(x) that are appropriate for measurement and experimental inaccuracies are derived. These new condition numbers must be compared with the established condition numbers, which are appropriate for quantifying the effect of roundoff errors due to floating point arithmetic. It is shown that the condition numbers that are derived in this paper may be considered average case (as opposed to worst case) because extensive use is made of the expected values of random variables and functions of random variables. Specifically, it is assumed that each coefficient of p(x) is perturbed by an independent zero mean Gaussian random variable, and a measure of the condition of x₀ is defined as the ratio of the expected value of its relative error to the expected value of the relative error in the coefficients of p(x), defined in both the componentwise and normwise forms. It is shown that this distinction between the componentwise and normwise condition estimates is important because they may differ by several orders of magnitude, depending on the coefficients of the polynomial. The cause of ill-conditioning of multiple roots is considered and it is shown that the situations m = 1 and m > 1 must be treated separately. Computational experiments that illustrate the theoretical results are presented.     

An algorithm for locating all zeros of a real polynomial

We present a globally convergent algorithm for calculating all zeros of a polynomialp _n ,p _n (z) = ∑ _{v = 0} ⁿ a _v z ^v, with real coefficients. Splittingp _n (exp(it)) into its real and imaginary part we can decide via Euclidean division of Chebyshev expansions and Sturm sequence argumentations whetherp _n has some zeros on the unit circle and how many zeros lie on the boundary and in the interior of it. Hence, by a bisection strategy we get the moduli of all zeros to a prescribed accuracy, and additionally we find the arguments as real zeros of a low degree polynomial. In this way we generate starting approximations for all zeros which in a final step are refined by an iterative process of higher order of convergence (e.g. Newton's or Bairstow's method).     

Exact Complexity of the Winner Problem for Young Elections

In 1977 Young proposed a voting scheme that extends the Condorcet Principle based on the fewest possible number of voters whose removal yields a Condorcet winner. We prove that both the winner and the ranking problem for Young elections is complete for \p _|| ^NP , the class of problems solvable in polynomial time by parallel access to NP. Analogous results for Lewis Carroll's 1876 voting scheme were recently established by Hemaspaandra et al. In contrast, we prove that the winner and ranking problems in Fishburn's homogeneous variant of Carroll's voting scheme can be solved efficiently by linear programming.     

On the Complexity of Matroid Isomorphism Problem

We study the complexity of testing if two given matroids are isomorphic. The problem is easily seen to be in S₂^p\Sigma_{2}^{p}. In the case of linear matroids, which are represented over polynomially growing fields, we note that the problem is unlikely to be S₂^p\Sigma_{2}^{p}-complete and is co NP-hard. We show that when the rank of the matroid is bounded by a constant, linear matroid isomorphism, and matroid isomorphism are both polynomial time many-one equivalent to graph isomorphism.     

An approach to estimating the complexity of probabilistic procedures for the postoptimality analysis of discrete optimization problems

It is shown that ZPP- and RP-probabilistic polynomial postoptimality analysis procedures for finding an optimal solution of a set cover problem that differs from the original problem in one position of the constraints matrix do not exist if an optimal solution of the original problem is known and if ZPP ?? NP (RP ?? NP). A similar result holds for the knapsack problem.     

Complexity of Weak Bisimilarity and Regularity for BPA and BPP

It is an open problem whether weak bisimilarity is decidable for Basic Process Algebra (BPA) and Basic Parallel Processes (BPP). A PSPACE lower bound for BPA and NP lower bound for BPP have been demonstrated by Stribrna. Mayr achieved recently a result, saying that weak bisimilarity for BPP is Π^p₂-hard. We improve this lower bound to PSPACE, moreover for the restricted class of normed BPP.Weak regularity (finiteness) of BPA and BPP is not known to be decidable either. In the case of BPP there is a Π^p₂-hardness result by Mayr, which we improve to PSPACE. No lower bound has previously been established for BPA. We demonstrate DP-hardness, which in particular implies both NP and co-NP-hardness.In each of the bisimulation/regularity problems we consider also the classes of normed processes.Note: full version of the paper appears as [18].     

Pólya’s Theorem with zeros

Let R[X] be the real polynomial ring in n variables. Pólya’s Theorem says that if a homogeneous polynomial p∈R[X] is positive on the standard n-simplex Δ_n, then for sufficiently large N all the coefficients of (X₁+?+X_n)^Np are positive. We give a complete characterization of forms, possibly with zeros on Δ_n, for which there exists N so that all coefficients of (X₁+?+X_n)^Np have only nonnegative coefficients, along with a bound on the N needed.     

Most Relevant Explanation: computational complexity and approximation methods

Most Relevant Explanation (MRE) is the problem of finding a partial instantiation of a set of target variables that maximizes the generalized Bayes factor as the explanation for given evidence in a Bayesian network. MRE has a huge solution space and is extremely difficult to solve in large Bayesian networks. In this paper, we first prove that MRE is at least NP-hard. We then define a subproblem of MRE called MRE _k that finds the most relevant k-ary explanation and prove that the decision problem of MRE _k is NP^PPNP^{\it PP}-complete. Since MRE needs to find the best solution by MRE _k over all k, and we can also show that MRE is in NP^PPNP^{\it PP}, we conjecture that a decision problem of MRE is NP^PPNP^{\it PP}-complete as well. Furthermore, we show that MRE remains in NP^PPNP^{\it PP} even if we restrict the number of target variables to be within a log factor of the number of all unobserved variables. These complexity results prompt us to develop a suite of approximation algorithms for solving MRE, One algorithm finds an MRE solution by integrating reversible-jump MCMC and simulated annealing in simulating a non-homogeneous Markov chain that eventually concentrates its mass on the mode of a distribution of the GBF scores of all solutions. The other algorithms are all instances of local search methods, including forward search, backward search, and tabu search. We tested these algorithms on a set of benchmark diagnostic Bayesian networks. Our empirical results show that these methods could find optimal MRE solutions for most of the test cases in our experiments efficiently.     

An inductive number-theoretic characterization of NP

It is shown that NP equals the closure of λxyz.z = x*y (* denotes concatenation of numbers in m-adic notation) under ∨, &, (?x)_Py, (?x)_Py, (?x)_?y, explicit transformation and substitution of λxy.x^¦y¦ for a variable, where ¦ denotes m-adic le ngth.