Search

NP-complete problems should be hard on some instances but those may be extremely rare. On generic instances many such problems, especially related to random graphs, have been proven easy. We show the intractability of random instances of a graph coloring problem: this graph problem is hard on average unless all NP problem under all samplable (i.e., generatable in polynomial time) distributions are easy. Worst case reductions use special gadgets and typically map instances into a negligible fraction of possible outputs. Ours must output nearly random graphs and avoid any super-polynomial distortion of probabilities., 15 pages

The DP Hypothesis has recently come under intense criticism (Bruening 2009, Bruening et al. 2018). In the face of this criticism, several responses have been offered. This paper addresses three such responses and shows that they are without force. First, N-to-D movement is not necessary in Shona, as Carstens (2017) claims. Second, patterns of hybrid agreement in Bosnian-Croatian-Serbian do not require the DP Hypothesis, as Salzmann (2018) claims. Third, patterns of conventionalized expressions show that there is a close syntactic relation, possibly selection, between a selecting head and N, contra Salzmann (2018). The patterns of conventionalized expressions are incompatible with the DP Hypothesis and require that the head of the nominal is N, not any functional head. Functional heads inside nominals have to be dependents of the head N, not vice versa.

We study the reachability problems in various nondeterministic polynomial maps in \(\mathbb {Z}^n\). We prove that the reachability problem for very simple three-dimensional affine maps (with independent variables) is undecidable and is \(\texttt {PSPACE}\)-hard for two-dimensional quadratic maps. Then we show that the complexity of the reachability problem for maps without functions of the form \(\pm x+b\) is lower. In this case the reachability problem is \(\texttt {PSPACE}\)-complete in general, and \(\mathtt{NP}\)-hard for any fixed dimension. Finally we extend the model by considering maps as language acceptors and prove that the universality problem is undecidable for two-dimensional affine maps.

We initiate the study of a fundamental combinatorial problem: Given a capacitated graph $$G=(V,E)$$G=(V,E), find a shortest walk (“route”) from a source $${s\in V}$$s∈V to a destination $$t\in V$$t∈V that includes all vertices specified by a set $$WP \subseteq V$$WP⊆V: the waypoints. This Waypoint Routing Problem finds immediate applications in the context of modern networked systems. Our main contribution is an exact polynomial-time algorithm for graphs of bounded treewidth. We also show that if the number of waypoints is logarithmically bounded, exact polynomial-time algorithms exist even for general graphs. Our two algorithms provide an almost complete characterization of what can be solved exactly in polynomial time: we show that more general problems (e.g., on grid graphs of maximum degree 3, with slightly more waypoints) are computationally intractable.

We show that the open problem of the existence of a p-optimal proof system for SAT can be characterized in terms of total nondeterministic Turing machines. We prove that there exists a p-optimal proof system for SAT if and only if there exists a proof system h for SAT such that for any total nondeterministic Turing machine working in polynomial time its totality is provable with short proofs in h and these proofs can be efficiently constructed. We prove that the standard proof system for SAT (a satisfying truth assignment is a proof of a satisfiable propositional formula) is p-optimal if and only if for any total nondeterministic Turing machine working in polynomial time its totality is provable with short proofs in the standard proof system for SAT and these proofs can be efficiently constructed.

The P vs. NP problem arose from the question of whether exhaustive search is necessary for problems with short verifiable solutions. We do not know if even a slight algorithmic improvement over exhaustive search is universally possible for all NP problems, and to date no major consequences have been derived from the assumption that an improvement exists. We show that there are natural NP and BPP problems for which minor algorithmic improvements over the trivial deterministic simulation already entail lower bounds such as ${\sf NEXP} \not\subseteq {\sf P}/{\rm poly}$ and ${\sf LOGSPACE} \neq {\sf NP}$. These results are especially interesting given that similar improvements have been found for many other hard problems. Optimistically, one might hope our results suggest a new path to lower bounds; pessimistically, they show that carrying out the seemingly modest program of finding slightly better algorithms for all search problems may be extremely difficult (if not impossible). We also prove unconditional s...

This paper examines the correlation between numbers of computer cores in parallel genetic algorithms. The objective to determine the linear polynomial complementary equation in order represent the relation between number of parallel processing and optimum solutions. Model this relation as optimization function (f(x)) which able to produce many simulation results. F(x) performance is outperform genetic algorithms. Compression results between genetic algorithm and optimization function is done. Also the optimization function give model to speed up genetic algorithm. Optimization function is a complementary transformation which maps a TSP given to linear without changing the roots of the polynomials.

The more unambiguous statement of the P versus NP problem and the judgement of its hardness, are the key ways to find the full proof of the P versus NP problem. There are two sub-problems in the P versus NP problem. The first is the classifications of different mathematical problems (languages), and the second is the distinction between a non-deterministic Turing machine (NTM) and a deterministic Turing machine (DTM). The process of an NTM can be a power set of the corresponding DTM, which proves that the states of an NTM can be a power set of the corresponding DTM. If combining this viewpoint with Cantor’s theorem, it is shown that an NTM is not equipotent to a DTM. This means that “generating the power set P(A) of a set A” is a non-canonical example to support that P is not equal to NP.

An implicit characterization of the class NP is given, without using any minimization scheme. This is the first purely recursion-theoretic formulation of NP .

This article gives an overview of the geometric complexity theory (GCT) approach towards the P vs. NP and related problems focusing on its main complexity theoretic results. These are: (1) two concrete lower bounds, which are currently the best known lower bounds in the context of the P vs. NC and permanent vs. determinant problems, (2) the Flip Theorem, which formalizes the self-referential paradox in the P vs. NP problem, and (3) the Decomposition Theorem, which decomposes the arithmetic P vs. NP and permanent vs. determinant problems into subproblems without self-referential difficulty, consisting of positivity hypotheses in algebraic geometry and representation theory and easier hardness hypotheses.

We study the average-case hardness of the class NP against deterministic polynomial time algorithms. We prove that there exists some constant mu Gt 0 such that if there is some language in NP for which no deterministic polynomial time algorithm can decide L correctly on a 1 - (log n)-mu fraction of inputs of length n, then there is a language L' in NP for which no deterministic polynomial time algorithm can decide L' correctly on a 3/4 + (log n)-mu fraction of inputs of length n. In coding theoretic terms, we give a construction of a monotone code that can be uniquely decoded up to error rate 1/4 by a deterministic local decoder.

We study compression that preserves the solution to an instance of a problem rather than preserving the instance itself. Our focus is on the compressibility of $\mathcal{NP}$ decision problems. We consider $\mathcal{NP}$ problems that have long instances but relatively short witnesses. The question is whether one can efficiently compress an instance and store a shorter representation that maintains the information of whether the original input is in the language or not. We want the length of the compressed instance to be polynomial in the length of the witness and polylog in the length of original input. Such compression enables succinctly storing instances until a future setting will allow solving them, either via a technological or algorithmic breakthrough or simply until enough time has elapsed. In this paper, we first develop the basic complexity theory of compression, including reducibility, completeness, and a stratification of $\mathcal{NP}$ with respect to compression. We then show that compressibility (say, of SAT) would have vast implications for cryptography, including constructions of one-way functions and collision resistant hash functions from any hard-on-average problem in $\mathcal{NP}$ and cryptanalysis of key agreement protocols in the “bounded storage model” when mixed with (time) complexity-based cryptography.

We address the issue of inapproximability of the wavelength assignment problem in wavelength division multiplexing (WDM) optical networks. We prove that in an n-node WDM optical network with m lightpaths and maximum load L, if NP ≠ ZPP, for any constant δ>0, no polynomial time algorithm can achieve approximation ratio n1/2−δ or m1−δ, where NP is the class of problems which can be solved by nondeterministic polynomial time algorithms, and ZPP is the class of problems that can be solved by polynomial randomized algorithms with zero probability of error. Furthermore, the above result still holds even when L=2. We also prove that no algorithm can guarantee the number of wavelengths to be less than $$(\sqrt{n}/2)L$$ or (m/2)L. This is the first time inapproximability results are established for the wavelength assignment problem in WDM optical networks. We also notice the following fact, namely, there is a polynomial time algorithm for wavelength assignment which achieves approximation ratio of O(m(log log m)2/(log m)3). Therefore, the above lower bound of m1−δ is nearly tight.

We consider three complexity classes defined on Accepting Hybrid Networks of Evolutionary Processors (AHNEP) and compare them with the classical complexity classes defined on the standard computing model of Turing machine. By definition, AHNEPs are deterministic. We prove that the classical complexity class NP equals the family of languages decided by AHNEPs in polynomial time. A language is in P if and only if it is decided by an AHNEP in polynomial time and space. We also show that PSPACE equals the family of languages decided by AHNEPs in polynomial length.

The inverse problem relative to a verifier V of proofs of membership for a NP language is the problem of deciding, given a set ? of proofs, whether or not there exists a string x having exactly ? as its set of proofs. In this paper, we study the complexity of inverse problems. We develop a new notion of reduction which allows one to compare the complexity of inverse problems. Using this notion, we classify as coNP-complete the inverse problems for the "natural" verifiers of many NP-complete problems. We also show that the inverse complexity of a verifier for a language L cannot be predicted solely from the complexity of L, but rather, is highly dependent upon the choice of verifier used to accept L. In this context, a verifier with a Σ 2 p -complete inverse problem is exhibited, giving a new and natural example of a Σ 2 p -complete problem.

Based on oracle Turing machines, we investigate the computational complexity of operators on compact sets. For the projection and convex hull we are able to show exponential upper and lower bounds as well as a connection to the P=NP problem for special settings.

We study the computational complexity of basic decision problems of 3-dimensional topology, such as to determine whether a triangulated 3-manifold is irreducible, prime, ∂-irreducible, or homeomorphic to a given 3-manifold M. For example, we prove that the problem to recognize whether a triangulated 3-manifold is homeomorphic to a 3-sphere, or to a 2-sphere bundle over a circle, or to a real projective 3-space, or to a handlebody of genus g, is decidable in nondeterministic polynomial time (NP) of size of the triangulation. We also show that the problem to determine whether a triangulated orientable 3-manifold is irreducible (or prime) is in PSPACE and whether it is ∂-irreducible is in coNP. The proofs improve and extend arguments of prior author’s article on the recognition problem for the 3-sphere.

The Turing and many-one completeness notions for NP have been previously separated under measure, genericity, and bi-immunity hypotheses on NP. The proofs of all these results rely on the existence of a language in NP with almost everywhere hardness. In this paper we separate the same NP-completeness notions under a partial bi-immunity hypothesis that is weaker and only yields a language in NP that is hard to solve on most strings. This improves the results of Lutz and Mayordomo (Theoretical Computer Science, 1996), Ambos-Spies and Bentzien (Journal of Computer and System Sciences, 2000), and Pavan and Selman (Information and Computation, 2004). The proof of this theorem is a significant departure from previous work. We also use this theorem to separate the NP-completeness notions under a scaled dimension hypothesis on NP.

Computational complexity of two-dimensional domains whose boundaries are polynomial-time computable Jordan curves with polynomial inverse moduli of continuity is studied. It is shown that the membership problem of such a domain can be solved in PNP, i.e., in polynomial time relative to an oracle in NP, in contrast to the higher upper bound PMP for domains without the property of polynomial inverse modulus of continuity. On the other hand, the lower bound of UP for the membership problem still holds for domains with polynomial inverse moduli of continuity. It is also shown that the shortest path problem of such a domain can be solved in PSPACE, close to its known lower bound, while no fixed upper bound was known for domains without this property.

We investigate the computational complexity of finding the minimum-area circumscribed rectangle of a given two-dimensional domain. We study this problem in the polynomial-time complexity theory of real functions based on the oracle Turing machine model. We show that a bounded domain S with a polynomial-time computable Jordan curve Γ as the boundary may not have a computable minimum-area circumscribed rectangle. We also show that the problem of finding the minimum area of a circumscribed rectangle of a polynomial-time computable Jordan curve Γ is equivalent to a discrete Σ2P-complete problem. The related problem of finding the circumscribed squares of a Jordan curve Γ is also studied. We show that for any polynomial-time computable Jordan curve Γ, there must exist at least one computable circumscribed square (not necessarily of the minimum area), but this square may have arbitrarily high complexity.

We give resource bounded versions of the Completeness Theorem for propositional and predicate logic. For example, it is well known that every computable consistent propositional theory has a computable complete consistent extension. We show that, when length is measured relative to the binary representation of natural numbers and formulas, every polynomial time decidable propositional theory has an exponential time (EXPTIME) complete consistent extension whereas there is a nondeterministic polynomial time (NP) decidable theory which has no polynomial time complete consistent extension when length is measured relative to the binary representation of natural numbers and formulas. It is well known that a propositional theory is axiomatizable (respectively decidable) if and only if it may be represented as the set of infinite paths through a computable tree (respectively a computable tree with no dead ends). We show that any polynomial time decidable theory may be represented as the set of paths through a polynomial time decidable tree. On the other hand, the statement that every polynomial time decidable tree represents the set of complete consistent extensions of some theory which is polynomial time decidable, relative to the tally representation of natural numbers and formulas, is equivalent to P = NP. For predicate logic, we develop a complexity theoretic version of the Henkin construction to prove a complexity theoretic version of the Completeness Theorem. Our results imply that that any polynomial space decidable theory Δ possesses a polynomial space computable model which is exponential space decidable and thus Δ has an exponential space complete consistent extension. Similar results are obtained for other notions of complexity.

Motivated by recent results showing that there are natural parameterized problems that are fixed-parameter tractable, but can only be solved by fixed-parameter tractable algorithms the running time of which depends nonelementarily on the parameter, we propose a notion of bounded fixed-parameter tractability, where the dependence of the running time on the parameter is restricted to be singly exponential. We develop a basic theory that is centred around the class EPT of tractable problems and an EW-hierarchy of classes of intractable problems, both in the bounded sense. By and large, this theory is similar to the established unbounded parameterized complexity theory, but there are some remarkable differences. Most notably, certain natural model-checking problems that are known to be fixed-parameter tractable in the unbounded sense have a very high complexity in the bounded theory. The problem of computing the VC-dimension of a family of sets, which is known to be complete for the class W[1] in the unbounded theory, is complete for the class EW[3] in the bounded theory. It turns out that our bounded parameterized complexity theory is closely related to the classical complexity theory of problems that can be solved by a nondeterministic polynomial time algorithm that only uses log^2n nondeterministic bits, and in particular to the classes LOGSNP and LOGNP introduced by Papadimitriou and Yannakakis.

We show that if an NP-complete problem has a nonadaptive self-corrector with respect to any samplable distribution, then coNP is contained in NP/poly and the polynomial hierarchy collapses to the third level. Feigenbaum and Fortnow [SIAM J. Comput., 22 (1993), pp. 994-1005] show the same conclusion under the stronger assumption that an NP-complete problem has a nonadaptive random self-reduction. A self-corrector for a language L with respect to a distribution $\cal D$ is a worst-case to average-case reduction that transforms any given algorithm that correctly decides $L$ on most inputs (with respect to $\cal D$) into an algorithm of comparable efficiency that decides L correctly on every input. A random self-reduction is a special case of a self-corrector, where the reduction, given an input $x$, is restricted to only making oracle queries that are distributed according to $\cal D$. The result of Feigenbaum and Fortnow depends essentially on the property that the distribution of each query in a random self-reduction is independent of the input of the reduction. Our result implies that the average-case hardness of a problem in NP or the security of a one-way function cannot be based on the worst-case complexity of an NP-complete problem via nonadaptive reductions (unless the polynomial hierarchy collapses).

Extending results of Schindler, Hamkins and Welch, we establish in the context of infinite time Turing machines that P is properly contained in NP ∩ co-NP. For higher analogues of these classes, we exhibit positive and negative results.

We study the computational complexity of the distance function associated with a polynomial-time computable two-dimensional domains, in the context of the Turing machine-based complexity theory of real functions. It is proved that the distance function is not necessarily computable even if a two-dimensional domain is polynomial-time recognizable. On the other hand, if both the domain and its complement are strongly polynomial-time recognizable, then the distance function is polynomial-time computable if and only if P=NP.

The boolean hierarchy of k-partitions over NP for k ≥ 3 was introduced as a generalization of the well-known boolean hierarchy of sets (2-partitions). The classes of this hierarchy are exactly those classes of NP-partitions which are generated by finite labeled lattices. We generalize the boolean hierarchy of NP-partitions by studying partition classes which are defined by finite labeled posets. We give an exhaustive answer to the question of which relativizable inclusions between partition classes can occur depending on the relation between their defining posets. This provides additional evidence for the validity of the Embedding Conjecture for lattices.The study of the generalized boolean hierarchy is closely related to the issue of whether one can reduce the number of solutions of NP problems. For finite cardinality types, assuming the generalized boolean hierarchy of k-partitions over NP is strict, we give a complete characterization when such solution reductions are possible. This resolves in some sense an open question by Hemaspaandra et al.

Rice's Theorem states that all nontrivial language properties of recursively enumerable sets are undecidable. Borchert and Stephan (Math. Logic Quart. 46 (4) (2000) 489–504) started the search for complexity-theoretic analogs of Rice's Theorem, and proved that every nontrivial counting property of boolean circuits is UP-hard. Hemaspaandra and Rothe (Theoret. Comput. Sci. 244 (1–2) (2000) 205–217) improved the UP-hardness lower bound to UPO(1)-hardness. The present paper raises the lower bound for nontrivial counting properties from UPO(1)-hardness to FewP-hardness, i.e., from constant-ambiguity nondeterminism to polynomial-ambiguity nondeterminism. Furthermore, we prove that no relativizable technique can raise this lower bound to FewP-⩽1-ttp-hardness. We also prove a Rice-style theorem for NP, namely that every nontrivial language property of NP sets is NP-hard, and for a broad class of leaf-language classes we prove a sufficient condition for the natural analog of Rice's Theorem to hold.

In this paper, I discuss some properties of two functions, which I call f1() and f2(), which are interesting from the point of view of the P ?= NP problem. The both functions f1() and f2() concern the problem of solving a nondeterministic polynomial-time problem deterministically in a polynomial time. Based on the results, I finally outline a research program to study the P ?= NP problem.

This paper originates from the observation that many classical NP graph problems, including some NP-complete problems, are actually of very low nondeterministic time complexity. In order to formalize this observation, we define the complexity class vertexNLIN, which collects the graph problems computable on a nondeterministic RAM in time O(n), where n is the number of vertices of the input graph G=(V,E), rather than its usual size |V|+|E|. It appears that this class is robust (it is defined by a natural restrictive computational device; it is logically characterized by several simple fragments of existential second-order logic; it is closed under various combinatorial operators, including some restrictions of transitive closure) and meaningful (it contains many natural NP problems: connectivity, hamiltonicity, non-planarity, etc.). Furthermore, the very restrictive definition of vertexNLIN seems to have beneficial effects on our ability to answer difficult questions about complexity lower bounds or separation between determinism and nondeterminism. For instance, we prove that vertexNLIN strictly contains its deterministic counterpart, vertexDLIN, and even that it does not coincide with its complementary class, co-vertexNLIN. Also, we prove that several famous graph problems (e.g. planarity, 2-colourability) do not belong to vertexNLIN, although they are computable in deterministic time O(|V|+|E|).

We look at the hypothesis that all honest onto polynomial-time computable functions have a polynomial-time computable inverse. We show this hypothesis equivalent to several other complexity conjectures including:•In polynomial time, one can find accepting paths of nondeterministic polynomial-time Turing machines that accept Σ*.•Every total multivalued nondeterministic function has a polynomial-time computable refinement.•In polynomial time, one can compute satisfying assignments for any polynomial-time computable set of satisfiable formulae.•In polynomial time, one can convert the accepting computations of any nondeterministic Turing machine that accepts SAT to satisfying assignments. We compare these hypotheses with several other important complexity statements. We also examine the complexity of these statements where we only require a single bit instead of the entire inverse.

In this paper, we prove under a plausible complexity hypothesis that Reduced Error Pruning of branching programs is hard to approximate within log1-δ n, for every δ > 0, where n is the number of description variables, a measure of the problem's complexity. The result holds under the assumption that NP problems do not admit deterministic, slightly superpolynomial time algorithms: NP ⊄ TIME(|I|O(loglog |I|)). This improves on a previous result that only had a small constant inapproximability ratio, and puts a fairly strong constraint on the efficiency of potential approximation algorithms. The result also holds for read-once and µ-branching programs.

We consider uniform and non-uniform assumptions for the hardness of an explicit problem from finite state automata theory. First we show that a small improvement in the known straightforward algorithm for this problem can be used to design faster algorithms for subset sum and factoring, and improved deterministic simulations for non-deterministic time. On the other hand, we can use the same improved algorithm for our FSA problem to prove complexity class separation results (NL is not equal to P, or NP for the non-uniform case). This result can be viewed either as a hardness result for the FSA intersection problem, or as a method for separating NL from P or NP. It is interesting to note that this approach is based on a more general method for separating two complexity classes, using algorithms rather than lower bounds. (C) 2002 Elsevier Science B.V. All rights reserved. Theoretical Computer Science

This paper investigates nondeterministic bounded query classes in relation to the complexity of NP-hard approximation problems and the Boolean Hierarchy. Nondeterministic bounded query classes turn out be rather suitable for describing the complexity of NP-hard approximation problems. The results in this paper take advantage of this machine-based model to prove that in many cases, NP-approximation problems have the upward collapse property. That is, a reduction between NP-approximation problems of apparently different complexity at a lower level results in a similar reduction at a higher level. For example, if MAXCLIQUE reduces to (log n)-approximating MAXCLIQUE using many–one reductions, then the Traveling Salesman Problem (TSP) is equivalent to MAXCLIQUE under many–one reductions. Several upward collapse theorems are presented in this paper. The proofs of these theorems rely heavily on the machinery provided by the nondeterministic bounded query classes. In fact, these results depend on a surprising connection between the Boolean hierarchy and nondeterministic bounded query classes.

We give new positive and negative results (some conditional) on speeding up computational algebraic geometry over the reals: (1) A new and sharper upper bound on the number of connected components of a semialgebraic set. Our bound is novel in that it is stated in terms of the volumes of certain polytopes and, for a large class of inputs, beats the best previous bounds by a factor exponential in the number of variables. (2) A new algorithm for approximating the real roots of certain sparse polynomial systems. Two features of our algorithm are (a) arithmetic complexity polylogarithmic in the degree of the underlying complex variety (as opposed to the super-linear dependence in earlier algorithms) and (b) a simple and efficient generalization to certain univariate exponential sums. (3) Detecting whether a real algebraic surface (given as the common zero set of some input straight-line programs) is not smooth can be done in polynomial time within the classical Turing model (resp. BSS model over C) only if P=NP (resp. NP, This is the final journal version which will appear in Journal of Complexity. More typos are corrected, and a new section is added where the bounds here are compared to an earlier result of Benedetti, Loeser, and Risler. The LaTeX source needs the ajour.cls macro file to compile

We give the first nontrivial model-independent time–space tradeoffs for satisfiability. Namely, we show that SAT cannot be solved in n1+o(1) time and n1−ε space for any ε>0 general random-access nondeterministic Turing machines. In particular, SAT cannot be solved deterministically by a Turing machine using quasilinear time and n space. We also give lower bounds for log-space uniform NC1 circuits and branching programs. Our proof uses two basic ideas. First we show that if SAT can be solved nondeterministically with a small amount of time then we can collapse a nonconstant number of levels of the polynomial-time hierarchy. We combine this work with a result of Nepomnjaščiı that shows that a nondeterministic computation of superlinear time and sublinear space can be simulated in alternating linear time. A simple diagonalization yields our main result. We discuss how these bounds lead to a new approach to separating the complexity classes NL and NP. We give some possibilities and limitations of this approach.

Matroids and oriented matroids are fundamental objects in combinatorial geometry. While matroids model the behavior of vector configurations over general fields, oriented matroids model the behavior of vector configurations over ordered fields. For every oriented matroid there is a corresponding underlying matroid. This article addresses the question how complex it is to algorithmically decide whether, on the other hand, one can assign an orientation to a given (rank 3) matroid. We will prove that this problem is NP-complete.

A notion of complexity for an arbitrary structure was defined in the book of Poizat Les petits cailloux (1995): we can define P and NP problems over a differential field K. Using the Witness Theorem of Blum et al., we prove the P-stability of the theory of differential fields: a P problem over a differential field K is still P when restricts to a sub-differential field k of K. As a consequence, if P = NP over some differentially closed field K, then P = NP over any differentially closed field and over any algebraically closed field.

The Monte Carlo optimisation technique simulated annealing has been used to sample the possible values of the permanent of fully indecomposable (0,1)-matrices. The basic idea in simulated annealing is that a Markov chain explores the space of feasible solutions, each of which has an associated “energy” (here minus the permanent of the matrix). The control parameter “temperature” is gradually reduced in order to focus the search on the low-energy region of state space and eventually reaching the minimum. Although the minimum energy per se (largest permanent) is known, the spectrum above the minimum is not, so this importance sampling technique is quite efficient. Interest in permanents is based on the fact that it is “complete” for the class # P of enumeration problems, that is as hard as counting the number of accepting computations of any nondeterministic polynomial time Turing machine. The spectrum of possible values for the permanent of a (0, 1)-matrix with given topological dimension d is quite interesting but only partially understood. The present work is an experimental study of this spectrum using the handle basis representation of directed graphs and simulated annealing to sample the possible values. The results show that gaps exist in the spectrum of values of the permanent but also show the existence of values for d = 8 and 9 not hitherto observed. The new values in the spectrum of the permanent for d = 8 is 72 and for d = 9 are 119, 132, 136, 138, and 140. Further we found that the density of states grows exponentially with the permanent values. The larger the value of the permanent the larger the number of neighbours and the larger the energy barriers between the permanent values of the neighbours.

Papadimitriou introduced several classes of NP search problems based on combinatorial principles which guarantee the existence of solutions to the problems. Many interesting search problems not known to be solvable in polynomial time are contained in these classes, and a number of them are complete problems. We consider the question of the relative complexity of these search problem classes. We prove several separations which show that in a generic relativized world the search classes are distinct and there is a standard search problem in each of them that is not computationally equivalent to any decision problem. (Naturally, absolute separations would imply thatP≠NP.) Our separation proofs have interesting combinatorial content and go to the heart of the combinatorial principles on which the classes are based. We derive one result via new lower bounds on the degrees of poly- nomials asserted to exist by Hilbert's nullstellensatz over finite fields.

We resume computational complexity aspects of several models of membrane systems, namely P systems with active membranes, P systems with proteins on membranes and tissue P systems both with membrane separation and membrane division. A sequence of common issues is studied in relation to these P system models, and 16 open problems are stated in the text. We question the role of families of P systems and their necessity to solve computationally hard problems in polynomial time. For each P system model we focus on conditions guaranteeing the polynomial equivalence of families of P systems and Turing machines. The ability of P systems to solve NP/co-NP-complete problems in polynomial time (trading space for time) is a very popular issue. Interesting characterizations of the borderline between tractability and intractability, i.e., P/NP, have been recently shown. Similarly important, although less popular, is the relation between NP/co-NP and further classes as PP, the polynomial hierarchy PH and PSPACE. Several models of P systems has been shown to characterize the class PSPACE which itself characterizes parallel computations with an unlimited number of processors but a limited propagation of data between them.

This paper aims to provide a comparison between the notion of T time on average over ranking of distributions, proposed by Reischuk and Schindelhauer (1993), and the notion of T time on average, proposed by Ben-David et al. (1992). The latter is a direct generalization of Levin's notion of average polynomial time (Levin, 1986). In particular, we show that for any problem D and any ranking function ρ, if ρ(D) is solvable in time T on average over a uniform distribution and ρ is computable in polynomial time, then Dis solvable in time T ο p + q on average over ρ, where p and q are polynomials depending on ρ. We then show that, under a randomized reduction, there is a complete problem (D,ρ) for distributional NP problems with respect to ranking such that ρ(D) ϵ NP and if ρ(D) is solvable in time T on average over a uniform distribution, then D is solvable in time T(O(n)) + p(n) on average over ρ, where p is the time bound for computing ρ. Hence, no NP problems averaging over ranking of distributions are harder than averaging over uniform distributions in the notions of polynomial-time or sub-exponential-time solvability. Finally, we show that there is a reasonable tight hierarchy for the notion of T time on average over uniform distributions.

We propose a weak version of the Blum–Shub–Smale model of computation over the real numbers. In this weak model only a “moderate” usage of multiplications and divisions is allowed. The class of boolean languages recognizable in polynomial time is shown to be the complexity class P/poly. The main tool is a result on the existence of small rational points in semi-algebraic sets which is of independent interest. As an application, we generalize recent results of Siegelmann and Sontag on recurrent neural networks, and of Maass on feedforward nets. A preliminary version of this paper was presented at the1993 IEEE Symposium on Foundations of Computer Science. Additional results include: an efficient simulation of order-free real Turing machines by probabilistic Turing machines in the full Blum–Shub–Smale model; the strict inclusion of the real polynomial hierarchy in weak exponential time.

Let DLIN denote the class of problems that are computable withinO(n/logn) uniform time on a RAM which can read its input (of lengthn) in blocks and which only uses integersO(n/logn). We prove that the sorting problem belongs to DLIN and formulate the Linear Time Thesis: “Each problem computable by a linear time bounded algorithm (in an intuitive sense) belongs to DLIN”. We also study the subclass DTIMESORT(n) of problems computable within linear time on a Turing machine using in addition a fixed number of sortings, and we show how the reductions of this class, so-called sort-lin reductions, are useful to classify NP problems: e.g. there is a sort-lin reduction from SAT to 3-SAT (using no sorting) and a sort-lin reduction from the NP-complete graph problem KERNEL to SAT (but we do not know of any similar reduction in DTIME(n)). Similarly, problem 2-SAT is linearly equivalent to the problem of Horn renaming (via sort-lin reductions). Finally, SAT is compared with many other combinatorial problems. A problemA is SAT-easy (resp. SAT-hard) if there is a sort-lin reduction fromA to SAT (resp. SAT toA). A SAT-equivalent problem is a problem both SAT-easy and SAT-hard. It is shown that the class of SAT-easy (resp. SAT-equivalent) problems is very large and that its generalization to so-called special clauses or, more generally, regular clauses, does not enlarge it. Moreover, we justify our opinion that problem SAT is, in some sense, a minimal NP-complete problem.

The framework of Bodlaender et al. (ICALP 2008, JCSS 2009) and Fortnow and Santhanam (STOC 2008, JCSS 2011) allows us to exclude the existence of polynomial kernels for a range of problems under reasonable complexity-theoretical assumptions. However, some issues are not addressed by this framework, including the existence of Turing kernels such as the “kernelization” of Leaf Out Branching(k) into a disjunction over n instances each of size poly(k). Observing that Turing kernels are preserved by polynomial parametric transformations (PPTs), we define two kernelization hardness hierarchies by the PPT-closure of problems that seem fundamentally unlikely to admit efficient Turing kernelizations. This gives rise to the MK- and WK-hierarchies which are akin to the M- and W-hierarchies of ordinary parameterized complexity. We find that several previously considered problems are complete for the fundamental hardness class WK[1], including Min Ones d -SAT(k), Binary NDTM Halting(k), Connected Vertex Cover(k), and Clique parameterized by k logn. We conjecture that no WK[1]-hard problem admits a polynomial Turing kernel. Our hierarchy subsumes an earlier hierarchy of Harnik and Naor (FOCS 2006, SICOMP 2010) that, from a parameterized perspective, is restricted to classical problems parameterized by witness size. Our results provide the first natural complete problems for, e.g., their class VC 1; this had been left open.

This paper furthers the study of quasilinear-time complexity initiated by Schnorr and Gurevich and Shelah. We show that the fundamental properties of the polynomial-time hierarchy carry over to the quasilinear-time hierarchy. Whereas all previously known versions of the Valiant-Vazirani reduction from NP to parity run in quadratic time, we give a new construction using error-correcting codes that runs in quasilinear time. We show, however, that the important equivalence between search problems and decision problems in polynomial time is unlikely to carry over: if search reduces to decision for SAT in quasilinear time, then all of NP is contained in quasipolynomial time. Other connections are made to work by Stearns and Hunt on “power indices” of NP languages, and to work on bounded-query Turing reductions and helping by robust oracle machines.

A 2-1/2–dimensional (2-1/2D) boundary representation CAD data structure called rectangle adjacency graph (RAG) is presented. A review of nondeterministic polynomial (NP) completeness and proof of NP completeness of partition sequencing for a concrete placement process are provided. The proof is obtained by a polynomial transformation of the traveling salesman problem (TSP) which is known to be NP complete. An approximate algorithm that provides the best known ratio bound to TSP has been modified in order to develop a partition-sequencing algorithm that: (1) obtains appropriate cost functions between nonadjacent slabs; and (2) satisfies specific constraints related to concrete placement. The proposed partition-sequencing algorithm includes: (1) generating an appropriate cost function by obtaining the shortest path between each pair of odd-degree vertices in a minimum cost-spanning tree of RAG; (2) transforming the minimum cost-spanning tree of RAG into an Eulerian graph by duplicating edges that correspond...

The model of zero-knowledge multi-prover interactive proofs was introduced by Ben-Or, Goldwasser, Kilian and Wigderson in [4]. A major open problem associated with this model is whether NP problems can be proven by one-round, two-prover, zero-knowledge protocols with exponentially small error probability (e.g. via parallel executions). A positive answer was claimed by Fortnow, Rompel and Sipser in [12], but its proof was later shown to be flawed by Fortnow who demonstrated that the probability of cheating inn independent parallel rounds can be much higher than the probability of cheating inn independent sequential rounds (with exponential ratio between them). In this paper we solve this problem: We show a new one-round two-prover interactive proof for Graph Hamiltonicity, we prove that it is complete, sound and perfect zeroknowledge, and thus every problem in NP has a one-round two-prover interactive proof which is perfectly zero knowledge under no cryptographic assumptions. The main difficulty is in proving the soundness of our parallel protocol namely, proving that the probability of cheating in this one-round protocol is upper bounded by some exponentially low threshold. We prove that this probability is at most 1/2 n/9 (wheren is the number of parallel rounds), by translating the soundness problem into some extremal combinatorial problem, and then solving this new problem.