Search

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|).

LetAbe a finite, totally ordered alphabet, and let ⪯ be the lexicographic ordering onA*. LetXbe a subset ofA*. Thelanguage of minimal wordsofXis the subset ofXcomposed of the lexicographically minimal word ofXfor each length: Min(X)={x∈X| ∀w∈X, |w|=|x|⇒x⪯w}. The aim of this paper is to prove that ifLis a context-free language, then the language Min(L) context-free.

In this paper we introduce "hybrid" Max 2-CSP formulas consisting of "simple clauses", namely conjunctions and disjunctions of pairs of variables, and general 2-variable clauses, which can be any integer-valued functions of pairs of boolean variables. This allows an algorithm to use both efficient reductions specific to AND and OR clauses, and other powerful reductions that require the general CSP setting. We use new reductions introduced here, and recent reductions such as "clause-learning" and "2-reductions" generalized to our setting's mixture of simple and general clauses. Parametrizing an instance by the fraction p of non-simple clauses, we give an exact (exponential-time) algorithm that is the fastest known polynomial-space algorithm for p=0 (which includes the well-studied Max 2-Sat problem but also instances with arbitrary mixtures of AND and OR clauses); the only efficient algorithm for mixtures of AND, OR, and general integer-valued clauses; and tied for fastest for general Max 2-CSP (p=1). Since a pure 2-Sat input instance may be transformed to a general CSP instance in the course of being solved, the algorithm's efficiency and generality go hand in hand. Our algorithm analysis and optimization are a variation on the familiar measure-and-conquer approach, resulting in an optimizing mathematical program that is convex not merely quasi-convex, and thus can be solved efficiently and with a certificate of optimality. We produce a family of running-time upper-bound formulas, each optimized for instances with a particular value of p but valid for all instances., Comment: 40 pages, a preliminary version appeared in the proceedings of SODA 2009