Some observations on NP real numbers and P-selective sets

We show that each standard left cut of a real number is a p-selective set. Classification results about NP real numbers and recursively enumerable real numbers follow from similar results about p-selective and semirecursive sets. In particular, it is proved that no left cut can be NP-hard unless the polynomial hierarchy collapses to ?₂^P. This result is surprising because it shows that the McLaughlin-Martin construction of a ?_tt-complete r.e. semirecursive set fails at the polynomial time complexity level.     

Complexity in mechanized hypothesis formation

Practical questions of computability are studied for a special mechanized method designed to suggest scientific hypotheses on the basis of sampled data: the so-called GUHA method. In simplified terms our GUHA system accepts particular data as a binary (or, binary plus “x”: unknown) input matrix, which relates objects in the sample to a common set of yes-or-no properties. It seeks to output factual (non-tautologous) formal sentences, which are true in the data and so yield general hypotheses for the universe of all such objects. This paper is the first detailed analysis of the algorithmic complexity of this type of system, by considering the time (number of steps) needed to solve its basic decision problem: whether some factual sentence, of various pre-specified forms, will be so output. The resulting time bounds are functions of changeable input size and give minima for overall system complexity. In fact, when judged by the norm for efficient computability of polynomial-time, we present here both some positive and some closely related “negative” results: e.g. the distinction between P-time and NP-completeness (usually considered to be exponential time) often depends only on being given binary or ternary data, the basic question being existence of a true elementary disjunction.Quite similar results are true for sentences with either classical or non-classical (statistically motivated) quantifiers. Moreover, some closely related two-valued problems, involving input parameters to bound desired sentence length, resisted all our efforts to place them as P-time or NP-complete and have an apparently intermediate complexity. At least they are concrete candidates for the (theoretical) hierarchy of P-reducible degrees between P and NP (assuming P ≠ NP.     

The complexity of constraint satisfaction problems for small relation algebras

Andréka and Maddux [Notre Dame J. Formal Logic 35 (4) 1994] classified the small relation algebras—those with at most 8 elements, or in other terms, at most 3 atomic relations. They showed that there are eighteen isomorphism types of small relation algebras, all representable. For each simple, small relation algebra they computed the spectrum of the algebra, namely the set of cardinalities of square representations of that relation algebra.In this paper we analyze the computational complexity of the problem of deciding the satisfiability of a finite set of constraints built on any small relation algebra. We give a complete classification of the complexities of the general constraint satisfaction problem for small relation algebras. For three of the small relation algebras the constraint satisfaction problem is NP-complete, for the other fifteen small relation algebras the constraint satisfaction problem has cubic (or lower) complexity.We also classify the complexity of the constraint satisfaction problem over fixed finite representations of any relation algebra. If the representation has size two or less then the complexity is cubic (or lower), but if the representation is square, finite and bigger than two then the complexity is NP-complete.     

Maximum H-colourable subdigraphs and constraint optimization with arbitrary weights

In the maximum constraint satisfaction problem (Max CSP), one is given a finite collection of positive-weight constraints on overlapping sets of variables, and the goal is to assign values from a given domain to the variables so that the total weight of satisfied constraints is maximized. We consider this problem and its variant Max AW CSP where the weights are allowed to be both positive and negative, and study how the complexity of the problems depends on the allowed constraint types. We prove that Max AW CSP over an arbitrary finite domain exhibits a dichotomy: it is either polynomial-time solvable or NP-hard. Our proof builds on two results that may be of independent interest: one is that the problem of finding a maximum H-colourable subdigraph in a given digraph is either NP-hard or trivial depending on H, and the other a dichotomy result for Max CSP with a single allowed constraint type.     

The complexity of stochastic games

We consider the complexity of stochastic games—simple games of chance played by two players. We show that the problem of deciding which player has the greatest chance of winning the game is in the class NP co-NP.     

Some simplified NP-complete graph problems

It is widely believed that showing a problem to be NP-complete is tantamount to proving its computational intractability. In this paper we show that a number of NP-complete problems remain NP-complete even when their domains are substantially restricted. First we show the completeness of Simple Max Cut (Max Cut with edge weights restricted to value 1), and, as a corollary, the completeness of the Optimal Linear Arrangement problem. We then show that even if the domains of the Node Cover and Directed Hamiltonian Path problems are restricted to planar graphs, the two problems remain NP-complete, and that these and other graph problems remain NP-complete even when their domains are restricted to graphs with low node degrees. For Graph 3-Colorability, Node Cover, and Undirected Hamiltonian Circuit, we determine essentially the lowest possible upper bounds on node degree for which the problems remain NP-complete.     

On relativizations with restricted number of accesses to the oracle set

Conflicting relativizations, also known as Baker-Gill-Solovay phenomena, are common place in complexity theory. However, Book, Long, and Selman (SIAM J. Comput.,13 (1984), 461–487) have shown thatP(A) = NP _B (A) for all oraclesA if and only ifP = NP, whereNP _B (A) denotes the class of languages accepted by nondeterministic machines which possess only a polynomial number of query strings in the computation tree. It is shown in this paper that any superpolynomial bound on the number of queries already yields the BGS phenomenon. Similar results hold for theNP = co-NP andNPC = NP questions. A second objective of this paper is to point out a technique of Hartmanis with which to achieve oracle constructions by using the Kolmogorov complexity. This relatively new technique seems to be adequate for obtaining separation results for complexity classes which are not enumerable.     

Two-stage hybrid flow shop scheduling with dynamic job arrivals

Motivated by applications in semiconductor manufacturing industry, we consider a two-stage hybrid flow shop where a discrete machine is followed by a batching machine. In this paper, we analyze the computational complexity of a class of two-machine problems with dynamic job arrivals. For the problems belonging to P we present polynomial algorithms. For the NP-complete problems we propose the heuristics, and then establish the upper bounds on the worst case performance ratios of the heuristics. In addition, we give the improved heuristics that can achieve better performances.     

All Natural NP-Complete Problems Have Average-Case Complete Versions

The theory of average case complexity studies the expected complexity of computational tasks under various specific distributions on the instances, rather than their worst case complexity. Thus, this theory deals with distributional problems, defined as pairs each consisting of a decision problem and a probability distribution over the instances. While for applications utilizing hardness, such as cryptography, one seeks an efficient algorithm that outputs random instances of some problem that are hard for any algorithm with high probability, the resulting hard distributions in these cases are typically highly artificial, and do not establish the hardness of the problem under “interesting” or “natural” distributions. This paper studies the possibility of proving generic hardness results (i.e., for a wide class of NP{\mathcal{NP}} -complete problems), under “natural” distributions. Since it is not clear how to define a class of “natural” distributions for general NP{\mathcal{NP}} -complete problems, one possibility is to impose some strong computational constraint on the distributions, with the intention of this constraint being to force the distributions to “look natural”. Levin, in his seminal paper on average case complexity from 1984, defined such a class of distributions, which he called P-computable distributions. He then showed that the NP{\mathcal{NP}} -complete Tiling problem, under some P-computable distribution, is hard for the complexity class of distributional NP{\mathcal{NP}} problems (i.e. NP{\mathcal{NP}} with P-computable distributions). However, since then very few NP{\mathcal{NP}}- complete problems (coupled with P-computable distributions), and in particular “natural” problems, were shown to be hard in this sense. In this paper we show that all natural NP{\mathcal{NP}} -complete problems can be coupled with P-computable distributions such that the resulting distributional problem is hard for distributional NP{\mathcal{NP}}.     

VNS and second order heuristics for the min-degree constrained minimum spanning tree problem

Given an undirected graph with weights associated with its edges, the min-degree constrained minimum spanning tree (md$\mathit{md}$-MST) problem consists in finding a minimum spanning tree of the given graph, imposing minimum degree constraints in all nodes except the leaves. This problem was recently proposed in Almeida et al. [Min-degree constrained minimum spanning tree problem: Complexity, proprieties and formulations. Operations Research Center, University of Lisbon, Working-paper no. 6; 2006], where its theoretical complexity was characterized and showed to be NP$\mathit{NP}$-hard.     

Characterizing Linear Size Circuits in Terms of Privacy

In this paper we prove a perhaps unexpected relationship between the complexity class of the boolean functions that have linear size circuits andn-party private protocols. Specifically, letfbe a boolean function. We show thatfhas a linear size circuit if and only iffhas a 1-privaten-party protocol in which the total number of random bits used byallplayers is constant. From the point of view of complexity theory, our result gives a characterization of the class of linear size circuits in terms of another class of a very different nature. From the point of view of privacy, this result provides 1-private protocols that use a constant number of random bits, for many important functions for which no such protocol was previously known. On the other hand, our result suggests that proving, for anyNPfunction, that it has no 1-private constant-random protocol, might be difficult.     

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.     

Efficient approximation of min set cover by moderately exponential algorithms

We study the approximation of min set cover combining ideas and results from polynomial approximation and from exact computation (with non-trivial worst case complexity upper bounds) for NP-hard problems. We design approximation algorithms for min set cover achieving ratios that cannot be achieved in polynomial time (unless problems in NP could be solved by slightly super-polynomial algorithms) with worst-case complexity much lower (though super-polynomial) than those of an exact computation.     

Minimum cost flows with minimum quantities

We consider a variant of the well-known minimum cost flow problem where the flow on each arc in the network is restricted to be either zero or above a given lower bound. The problem was recently shown to be weakly NP-complete even on series-parallel graphs. We start by showing that the problem is strongly NP-complete and cannot be approximated in polynomial time (unless P=NP) up to any polynomially computable function even when the graph is bipartite and the given instance is guaranteed to admit a feasible solution. Moreover, we present a pseudo-polynomial-time exact algorithm and a fully polynomial-time approximation scheme (FPTAS) for the problem on series-parallel graphs.     

NP对PP

主要目的是研究NP与PP的关系。引入了一个NP的等价的随机定义。基于此等价定义,定义了另一个随机复杂性类：SUPER－NP。虽然SUPER－NP与NP非常接近,但令人吃惊的是发现了PP包含于SUPER－NP,从而NP包含于PP包含于SUPER－NP。考虑到NP＝PCP（log,O(1))以及NP和SUPER－NP的相似性,也希望能通过证明SUPER－NP包含于PCP（log^2,O(1))来解决PP包含于PCP（log^2,O(1))的猜想。     

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 complexity of deciding avoidability of sets of partial words

Blanchet-Sadri et al. have shown that Avoidability, or the problem of deciding the avoidability of a finite set of partial words over an alphabet of size k≥2, is NP-hard [F. Blanchet-Sadri, R. Jungers, J. Palumbo, Testing avoidability on sets of partial words is hard, Theoret. Comput. Sci. 410 (2009) 968-972]. Building on their work, we analyze in this paper the complexity of natural variations on the problem. While some of them are NP-hard, others are shown to be efficiently decidable. Using some combinatorial properties of de Bruijn graphs, we establish a correspondence between lengths of cycles in such graphs and periods of avoiding words, resulting in a tight bound for periods of avoiding words. We also prove that Avoidability can be solved in polynomial space, and reduces in polynomial time to the problem of deciding the avoidability of a finite set of partial words of equal length over the binary alphabet. We give a polynomial bound on the period of an infinite avoiding word, in the case of sets of full words, in terms of two parameters: the length and the number of words in the set. We give a polynomial space algorithm to decide if a finite set of partial words is avoided by a non-ultimately periodic infinite word. The same algorithm also decides if the number of words of length n avoiding a given finite set of partial words grows polynomially or exponentially with n.