Geometric optimization and the polynomial hierarchy

We illustrate two techniques of accurately classifying the optimization version of geometric problems in the polynomial hierarchy. We show that if NP ≠ Co-NP, then there are interesting natural geometric optimization problems (location-allocation problems under minsum) in Δ^P₂ that are in neither NP nor Co-NP. Hence, all these problems are shown to belong properly to Δ^P₂, the second level of the polynomial hierarchy. We also show that there are some interesting geometric optimization problems (location-allocation problems under minmax) complete for a class D^P (which is contained in Δ^P₂ and contains NP ∪ Co-NP).     

On lower bounds of the closeness between complexity classes

We show that if an NP-m-hard set is the union of a set in P_btt(Sparse) and the setA, then NP P_dtt(A). Since co-NP, R, and FewP are closed under _dtt ^P -reductions, so no NP-m-hard set is the union of a set in P_btt(Sparse) and a set in co-NP (resp. R, FewP) unless NP = co-NP (resp. NP = R, NP = FewP). We also study the distance between many important complexity classes. LetA,B be two sets. The distance function dist _A,B is defined as in [S1] such that dist _A,B (n) is the number of strings of length n inA B = (A – B) (B – A). We show that there exists a setA in p_{(k + 1)–tt}(Sparse) such that, for everyB in P _k–tt(Sparse), dist _A,B has an exponential lower bound.This research was supported in part by HTP 863.     

Oracle-dependent properties of the lattice of NP sets

We consider under the assumption P ≠ NP questions concerning the structure of the lattice of NP sets together with the sublattice P. We show that two questions which are slightly more complex than the known splitting properties of this lattice cannot be settled by arguments which relativize. The two questions which we consider are whether every infinite NP set contains an infinite P subset and whether there exists an NP-simple set. We construct several oracles, all of which make P ≠ NP, and which in addition make the above-mentioned statements either true or false. In particular we give a positive answer to the question, raised by Bennett and Gill (1981), whether an oracle B exists making P^B ≠ NP^B and such that every infinite set in NP^B has an infinite subset in P^B. The constructions of the oracles are finite injury priority arguments.     

On counting problems and the polynomial-time hierarchy

We consider the relation between the relativized polynomial time hierarchy and relativizations of Gill's class PP of sets recognizable in polynomial time by probabilistic Turing machines and of Valiant's class D≠P of sets polynomial time Turing reducible to functions that give the number of accepting computations of nondeterministic polynomial-time bounded Turing machines. The main result is that there exists an oracle set A such that PP^A ?(Π₂^P,A ∪ σ₂^P,A) ≠ ?, with the corollary that also D ≠P^A ? (Π₂^P,A ∪ σ₂^P,A ≠ ?. The proof is an application of Baker and Selman's technique for showing that σ₂^P,A ? σ₃^P,A for some oracle set A.     

Reductions on NP and P-selective sets

P-selective sets are used to distinguish polynomial time-bounded reducibilities on NP. In particular, we consider different kinds of “positive” reductions; these preserve membership in NP and are not a priori closed under complements. We show that the class of all sets which are both P-selective and have positive reductions to their complements is P. This is used to show that if DEXT ≠ NEXT, then there exists a set in NP?P that is not positive reducible to its complement. Various similar results are obtained. We also show that P is the class of all sets which are both p-selective and positive truth-table self-reducible. From this result, it follows that various naturally defined apparently intractible problems are not p-selective unless P = NP.     

Dominating Induced Matchings for P 7-Free Graphs in Linear Time

Let G be a finite undirected graph with edge set E. An edge set E′?E is an induced matching in G if the pairwise distance of the edges of E′ in G is at least two; E′ is dominating in G if every edge e∈E?E′ intersects some edge in E′. The Dominating Induced Matching Problem (DIM, for short) asks for the existence of an induced matching E′ which is also dominating in G; this problem is also known as the Efficient Edge Domination Problem. The DIM problem is related to parallel resource allocation problems, encoding theory and network routing. It is ${\mathbb{NP}}$ -complete even for very restricted graph classes such as planar bipartite graphs with maximum degree three. However, its complexity was open for P _k -free graphs for any k≥5; P _k denotes a chordless path with k vertices and k?1 edges. We show in this paper that the weighted DIM problem is solvable in linear time for P ₇-free graphs in a robust way.     

Polynomial Kernelizations for MIN F+Π1 and MAX NP

It has been observed in many places that constant-factor approximable problems often admit polynomial or even linear problem kernels for their decision versions, e.g., Vertex Cover, Feedback Vertex Set, and Triangle Packing. While there exist examples like Bin Packing, which does not admit any kernel unless P = NP, there apparently is a strong relation between these two polynomial-time techniques. We add to this picture by showing that the natural decision versions of all problems in two prominent classes of constant-factor approximable problems, namely MIN F⁺Π₁ and MAX NP, admit polynomial problem kernels. Problems in MAX SNP, a subclass of MAX NP, are shown to admit kernels with a linear base set, e.g., the set of vertices of a graph. This extends results of Cai and Chen (J. Comput. Syst. Sci. 54(3): 465–474, 1997), stating that the standard parameterizations of problems in MAX SNP and MIN F⁺Π₁ are fixed-parameter tractable, and complements recent research on problems that do not admit polynomial kernelizations (Bodlaender et al. in J. Comput. Syst. Sci. 75(8): 423–434, 2009).     

On the (Non-)Existence of Polynomial Kernels for P l -Free Edge Modification Problems

Given a graph G=(V,E) and a positive integer k, an edge modification problem for a graph property Π consists in deciding whether there exists a set F of pairs of V of size at most k such that the graph $H=(V,E\vartriangle F)$ satisfies the property Π. In the Π edge-completion problem, the set F is constrained to be disjoint from E; in the Π edge-deletion problem, F is a subset of E; no constraint is imposed on F in the Π edge-editing problem. A number of optimization problems can be expressed in terms of graph modification problems which have been extensively studied in the context of parameterized complexity (Cai in Inf. Process. Lett. 58:171–176, 1996; Fellows et al. in FCT, pp. 312–321, 2007; Heggernes et al. in STOC, pp. 374–381, 2007). When parameterized by the size k of the set F, it has been proved that if Π is a hereditary property characterized by a finite set of forbidden induced subgraphs, then the three Π edge-modification problems are FPT (Cai in Inf. Process. Lett. 58:171–176, 1996). It was then natural to ask (Bodlaender et al. in IWPEC, 2006) whether these problems also admit a polynomial kernel. in polynomial time to an equivalent instance (G′,k′) with size bounded by a polynomial in k). Using recent lower bound techniques, Kratsch and Wahlström answered this question negatively (Kratsch and Wahlström in IWPEC, pp. 264–275, 2009). However, the problem remains open on many natural graph classes characterized by forbidden induced subgraphs. question to characterize for which type of graph properties, the parameterized edge-modification problems have polynomial kernels. Kratsch and Wahlström asked whether the result holds when the forbidden subgraphs are paths or cycles and pointed out that the problem is already open in the case of P ₄-free graphs (i.e. cographs). This paper provides positive and negative results in that line of research. We prove that Parameterized cograph edge-modification problems have cubic vertex kernels whereas polynomial kernels are unlikely to exist for the P _l -free edge-deletion and the C _l -free edge-deletion problems for l?7 and l≥4 respectively. Indeed, if they exist, then NP?coNP/poly.     

Refuting learning revisited

We consider, within the framework of inductive inference, the concept of refuting learning as introduced by Mukouchi and Arikawa, where the learner is not only required to learn all concepts in a given class but also has to explicitly refute concepts outside the class.In the first part of the paper, we consider learning from text and introduce a concept of limit-refuting learning that is intermediate between refuting learning and reliable learning. We give characterizations for these concepts and show some results about their relative strength and their relation to confident learning.In the second part of the paper we consider learning from texts that for some k contain all positive Π_k-formulae that are valid in the standard structure determined by the set to be learned. In this model, the following results are shown. For the language with successor, any countable axiomatizable class can be limit-refuting learned from Π₁-texts. For the language with successor and order, any countable axiomatizable class can be reliably learned from Π₁-texts and can be limit-refuting learned from Π₂-texts, whereas the axiomatizable class of all finite sets cannot be limit-refuting learned from Π₁-texts. For the full language of arithmetic, which contains in addition plus and times, for any even k there is an axiomatizable class that can be limit-refuting learned from Π_k+1-texts but not from Π_k-texts. A similar result with k+3 in place of k+1 holds with respect to the language of Presburger's arithmetic.     

Honest polynomial degrees and P=? NP

We present a relatively simple proof of a result from Homer (1986) showing that if nonrecursive sets cannot be minimal for honest polynomial-time Turing reducibility (⩽^h_T-minimal), then P ≠ NP. As a corollary to our proof, we strengthen Homer's result by showing, without assuming that P ≠ NP, that there are ⩽^h_T-minimal sets for all tally sets. We also consider the converse of Homer's result, providing some evidence that the nonexistence of ⩽^h_T-minimal sets may folow from P ≠ NP in an interesting way. Finally, we consider structural and/or computability properties of sets that cannot be ⩽^h_T-minimal.     

Some Results on Derandomization

We show several results about derandomization including: 1. If NP is easy on average then efficient pseudorandom generators exist and P=BPP. 2. If NP is easy on average then given an NP machine M we can easily on average find accepting computations of M(x) when it accepts. 3. For any A in EXP, if NEXP^A is in P^A/poly then NEXP^A=EXP^A. 4.If A is ^p_k and NEXP^A is in P^A/poly then NEXP^A=EXP=MA^A.     

Convergence of Map Seeking Circuits

The map-seeking circuit (MSC) is an explicit biologically-motivated computational mechanism which provides practical solution of problems in object recognition, image registration and stabilization, limb inverse-kinematics and other inverse problems which involve transformation discovery. We formulate this algorithm as discrete dynamical system on a set Δ=Π _?=1 ^L Δ^(?), where each Δ^(?) is a compact subset of a nonnegative orthant of ? ⁿ , and show that for an open and dense set of initial conditions in Δ the corresponding solutions converge to either a vector with unique nonzero element in each Δ^(?) or to a zero vector. The first result implies that the circuit finds a unique best mapping which relates reference pattern to a target pattern; the second result is interpreted as “no match found”. These results verify numerically observed behavior in numerous practical applications.     

Exact exponential-time algorithms for finding bicliques

Due to a large number of applications, bicliques of graphs have been widely considered in the literature. This paper focuses on non-induced bicliques. Given a graph G=(V,E) on n vertices, a pair (X,Y), with X,Y⊆V, X∩Y=∅, is a non-induced biclique if {x,y}∈E for any x∈X and y∈Y. The NP-complete problem of finding a non-induced (k₁,k₂)-biclique asks to decide whether G contains a non-induced biclique (X,Y) such that |X|=k₁ and |Y|=k₂. In this paper, we design a polynomial-space O(n^1.6914)-time algorithm for this problem. It is based on an algorithm for bipartite graphs that runs in time O(n^1.30052). In deriving this algorithm, we also exhibit a relation to the spare allocation problem known from memory chip fabrication. As a byproduct, we show that the constraint bipartite vertex cover problem can be solved in time O(n^1.30052).     

Consensus seeking in a network of discrete-time linear agents with communication noises

This paper studies the mean square consensus of discrete-time linear time-invariant multi-agent systems with communication noises. A distributed consensus protocol, which is composed of the agent's own state feedback and the relative states between the agent and its neighbours, is proposed. A time-varying consensus gain a[k] is applied to attenuate the effect of noises which inherits in the inaccurate measurement of relative states with neighbours. A polynomial, namely ‘parameter polynomial’, is constructed. And its coefficients are the parameters in the feedback gain vector of the proposed protocol. It turns out that the parameter polynomial plays an important role in guaranteeing the consensus of linear multi-agent systems. By the proposed protocol, necessary and sufficient conditions for mean square consensus are presented under different topology conditions: (1) if the communication topology graph has a spanning tree and every node in the graph has at least one parent node, then the mean square consensus can be achieved if and only if ∑^∞_{k = 0}a[k] = ∞, ∑^∞_{k = 0}a²[k] < ∞ and all roots of the parameter polynomial are in the unit circle; (2) if the communication topology graph has a spanning tree and there exits one node without any parent node (the leader–follower case), then the mean square consensus can be achieved if and only if ∑^∞_{k = 0}a[k] = ∞, lim_{k → ∞}a[k] = 0 and all roots of the parameter polynomial are in the unit circle; (3) if the communication topology graph does not have a spanning tree, then the mean square consensus can never be achieved. Finally, one simulation example on the multiple aircrafts system is provided to validate the theoretical analysis.     

On the Huffman and Alphabetic Tree Problem with General Cost Functions

We address generalized versions of the Huffman and Alphabetic Tree Problem where the cost caused by each individual leaf i, instead of being linear, depends on its depth in the tree by an arbitrary function. The objective is to minimize either the total cost or the maximum cost among all leaves. We review and extend the known results in this direction and devise a number of new algorithms and hardness proofs. It turns out that the Dynamic Programming approach for the Alphabetic Tree Problem can be extended to arbitrary cost functions, resulting in a time O(n ⁴) optimal algorithm using space O(n ³). We identify classes of cost functions where the well-known trick to reduce the runtime by a factor of n via a “monotonicity” property can be applied. For the generalized Huffman Tree Problem we show that even the k-ary version can be solved by a generalized version of the Coin Collector Algorithm of Larmore and Hirschberg (in Proc. SODA’90, pp. 310–318, 1990) when the cost functions are nondecreasing and convex. Furthermore, we give an O(n ²logn) algorithm for the worst case minimization variants of both the Huffman and Alphabetic Tree Problem with nondecreasing cost functions. Investigating the limits of computational tractability, we show that the Huffman Tree Problem in its full generality is inapproximable unless P = NP, no matter if the objective function is the sum of leaf costs or their maximum. The alphabetic version becomes NP-hard when the leaf costs are interdependent.     

Properties of interval operators

In this paper we give some properties of interval operatorsF which guarantee the convergence of the interval sequence {X _k} defined byX _k+1:=F(X_k)∩X_k to a unique fixed interval \(\hat X\) . This interval \(\hat X\) encloses the “zero-set”X ^* of a function strip \(G(x): = [g(x),\bar g(x)]\) . for some known interval operators we investigate under which assumptions these properties are valid.     

Simulated annealing type algorithms for multivariate optimization

We study the convergence of a class of discrete-time continuous-state simulated annealing type algorithms for multivariate optimization. The general algorithm that we consider is of the formX _k +1 =X _k ?a _k (▽U(X _k ) + ξ_k) +b _k W _k . HereU(·) is a smooth function on a compact subset of ? ^d , {ξ_k} is a sequence of ? ^d -valued random variables, {W _k } is a sequence of independent standardd-dimensional Gaussian random variables, and {a _k }, {b _k } are sequences of positive numbers which tend to zero. These algorithms arise by adding decreasing white Gaussian noise to gradient descent, random search, and stochastic approximation algorithms. We show under suitable conditions onU(·), {ξ _k }, {a _k }, and {b _k } thatX _k converges in probability to the set of global minima ofU(·). A careful treatment of howX _k is restricted to a compact set and its effect on convergence is given.     

Some more independence results in complexity theory

A theorem of Hartmanis and Eopcroft is extended to obtain further independence results related to $\text{‘P = ?NP’}$. Alternative proofs are give for some of these results, following Hajek, obtaining Π₂⁰ and σ₂⁰ complete sets. It is pointed out however, that these theorems neither support the evidence for nor against the independence of P = NP.     

On the Connection Between the Correction and Weighting Functions in the Correction Procedure via Reconstruction Method

In this note, the connection between the correction and weighting functions for the correction procedure via reconstruction (CPR) method in 1D is addressed. A one-parameter family of weighting functions is constructed from the discontinuous test space. It is found that if the solution polynomials lie in the space P ^k , then the first k weighting functions can always be chosen as the basis of the polynomial space P ^k?1 and the last weighting function can be selected as a piece-wise continuous polynomial. There exists at least one set of weighting functions which can recover the energy stable flux reconstruction (ESFR) schemes. This strategy has been successfully applied to recover several known high-order discontinuous schemes, including DG, SD, SV, and Huynh??s g ₂ scheme.