Bounds for the Element Distinctness Problem on one-tape Turing machines

We disprove a conjecture of López-Ortiz by showing that the Element Distinctness Problem for n numbers of size O(logn) can be solved in O(n²(logn)^3/2(loglogn)^1/2) steps by a nondeterministic one-tape Turing machine. Further we give a simplified algorithm for solving the problem for shorter numbers in time O(n²logn) on a deterministic one-tape Turing machine and a new proof of the matching lower bound.     

Monotone Boolean dualization is in co-NP[logn]

In 1996, Fredman and Khachiyan [J. Algorithms 21 (1996) 618-628] presented a remarkable algorithm for the problem of checking the duality of a pair of monotone Boolean expressions in disjunctive normal form. Their algorithm runs in n^o(logn) time, thus giving evidence that the problem lies in an intermediate class between P and co-NP. In this paper we show that a modified version of their algorithm requires deterministic polynomial time plus O(log²n) nondeterministic guesses, thus placing the problem in the class co-NP[log²n]. Our nondeterministic version has also the advantage of having a simpler analysis than the deterministic one.     

Communicating processes,scheduling, and the complexity of nontermination

In this paper we study the computational complexity of the nontermination problem for systems of communicating processes with respect to five types of scheduling schemes, namely, round-robin, random, priority, first-come-first-served, and equifair schedules. We show that the problem is undecidable (₁-complete) with respect to round-robin, first-come-first-served, and priority scheduling; whereas it is decidable with respect to random and equifair scheduling. (Here ₁ denotes the set of languages whose complements are recursively enumerable.) For a restricted class of systems in which the communication channels between processes are of unit capacity, we show that the nontermination problem is solvable inO(k ² logn) nondeterministic space for round-robin, random, priority, and first-come-first-served scheduling, and inn ^{o(k 2}) nondeterministic time for equifair scheduling, wherek is the number of processes andn is the size of the maximal process. We are also able to establish a lower bound of ((k–59)/20*logn) nondeterministic space for all five types of scheduling schemes.     

Subexponential algorithms for partial cover problems

Partial Cover problems are optimization versions of fundamental and well-studied problems like Vertex Cover and Dominating Set. Here one is interested in covering (or dominating) the maximum number of edges (or vertices) using a given number k of vertices, rather than covering all edges (or vertices). In general graphs, these problems are hard for parameterized complexity classes when parameterized by k. It was recently shown by Amini et al. (2008) [1] that Partial Vertex Cover and Partial Dominating Set are fixed parameter tractable on large classes of sparse graphs, namely H-minor-free graphs, which include planar graphs and graphs of bounded genus. In particular, it was shown that on planar graphs both problems can be solved in time ²O(k)nO(1).During the last decade there has been an extensive study on parameterized subexponential algorithms. In particular, it was shown that the classical Vertex Cover and Dominating Set problems can be solved in subexponential time on H-minor-free graphs. The techniques developed to obtain subexponential algorithms for classical problems do not apply to partial cover problems. It was left as an open problem by Amini et al. (2008) [1] whether there is a subexponential algorithm for Partial Vertex Cover and Partial Dominating Set. In this paper, we answer the question affirmatively by solving both problems in time not only on planar graphs but also on much larger classes of graphs, namely, apex-minor-free graphs. Compared to previously known algorithms for these problems our algorithms are significantly faster and simpler.     

A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs

Branching programs are a well-established computation model for Boolean functions, especially read-once branching programs (BP1s) have been studied intensively. A very simple function f in n² variables is exhibited such that both the function f and its negation ¬f can be computed by Σ³_p-circuits, the function f has nondeterministic BP1s (with one nondeterministic node) of linear size and ¬f has size O(n⁴) for oblivious nondeterministic BP1s but f requires nondeterministic graph-driven BP1s of size . This answers an open question stated by Jukna, Razborov, Savický, and Wegener [Comput. Complexity 8 (1999) 357-370].     

Weighted broadcast in linear radio networks

The weighted version of the broadcast range assignment problem in ad hoc wireless network is studied. Efficient algorithms are presented for the unbounded and bounded-hop broadcast problems for the linear radio network, where radio stations are placed on a straight line. For the unbounded case of the problem, the proposed algorithm runs in O(n²) time and using O(n) space, where n is the number of radio stations in the network. For the h-hop broadcast problem, the time and space complexities of our algorithm are O(hn²logn) and O(hn), respectively. This improves time complexity of the existing results for the same two problems by a factor of n and , respectively [C. Ambuhl, A.E.F. Clementi, M.D. Ianni, G. Rossi, A. Monti, R. Silvestri, The range assignment problem in non-homogeneous static ad hoc networks, in: Proc. 18th Int. Parallel and Distributed Precessing Symposium, 2004].     

Tight lower bounds for certain parameterized NP-hard problems

Based on the framework of parameterized complexity theory, we derive tight lower bounds on the computational complexity for a number of well-known NP-hard problems. We start by proving a general result, namely that the parameterized weighted satisfiability problem on depth-t circuits cannot be solved in time n^o(k)m^O(1), where n is the circuit input length, m is the circuit size, and k is the parameter, unless the (t − 1)-st level W[t − 1] of the W-hierarchy collapses to FPT. By refining this technique, we prove that a group of parameterized NP-hard problems, including weighted sat, hitting set, set cover, and feature set, cannot be solved in time n^o(k)m^O(1), where n is the size of the universal set from which the k elements are to be selected and m is the instance size, unless the first level W[1] of the W-hierarchy collapses to FPT. We also prove that another group of parameterized problems which includes weighted q-sat (for any fixed q 2), clique, independent set, and dominating set, cannot be solved in time n^o(k) unless all search problems in the syntactic class SNP, introduced by Papadimitriou and Yannakakis, are solvable in subexponential time. Note that all these parameterized problems have trivial algorithms of running time either n^km^O(1) or O(n^k).     

Bounded Queries, Approximations, and the Boolean Hierarchy

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 M C reduces to (log n)-approximating M C using many–one reductions, then the Traveling Salesman Problem (TSP) is equivalent to M C 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.     

Gradually intractable problems and nondeterministic log-space lower bounds

The paper places five different problems (thek-pebble game problem, two problems aboutk finite automata, the reachability problem for Petri nets withk tokens, and the teachability problem for graphs whose k-dimensional edge sets are described by Cartesian products ofk factors) into the hierarchyNL _k of problems solvable by nondeterministic Turing machines ink-log₂ n space (and binary tape alphabet, to avoid tape speed-up). The results, when combined with the conjecture thatNL _i contains problems that requireO(n ^k ) deterministic time, show that these problems, while inP for every fixed value ofk, have polynomial deterministic time complexities with the degree of the polynomial growing linearly with the parameterk, and hence are, in this sense, gradually intractable.     

O(n) routing in rearrangeable networks

In (2n−1)-stage rearrangeable networks, the routing time for any arbitrary permutation is Ω(n²) compared to its propagation delay O(n) only. Here, we attempt to identify the sets of permutations, which are routable in O(n) time in these networks. We define four classes of self-routable permutations for Benes network. An O(n) algorithm is presented here, that identifies if any permutation P belongs to one of the proposed self-routable classes, and if yes, it also generates the necessary control vectors for routing P. Therefore, the identification, as well as the switch setting, both problems are resolved in O(n) time by this algorithm. It covers all the permutations that are self-routable by anyone of the proposed techniques. Some interesting relationships are also explored among these four classes of permutations, by applying the concept of ‘group-transformations’ [N. Das, B.B. Bhattacharya, J. Dattagupta, Hierarchical classification of permutation classes in multistage interconnection networks, IEEE Trans. Comput. (1993) 665–677] on these permutations. The concepts developed here for Benes network, can easily be extended to a class of (2n−1)-stage networks, which are topologically equivalent to Benes network. As a result, the set of permutations routable in a (2n−1)-stage rearrangeable network, in a time comparable to its propagation delay has been extended to a large extent.     

Heuristics for the multi-item capacitated lot-sizing problem with lost sales

This paper deals with the multi-item capacitated lot-sizing problem with setup times and lost sales. Because of lost sales, demands can be partially or totally lost. To find a good lower bound, we use a Lagrangian relaxation of the capacity constraints, when single-item uncapacitated lot-sizing problems with lost sales have to be solved. Each subproblem is solved using an adaptation of the O(T²)$O(T^2)$ dynamic programming algorithm of Aksen et al. [5]. To find feasible solutions, we propose a non-myopic heuristic based on a probing strategy and a refining procedure. We also propose a metaheuristic based on the adaptive large neighborhood search principle to improve solutions. Some computational experiments showing the effectiveness and limitation of each approach are presented.     

Jebelean-Weber's algorithm without spurious factors

Tudor Jebelean and Ken Weber introduced an algorithm for finding (a,b)-pairs satisfying au+bv≡0 (mod k), with . It is based on Sorenson's “k-ary reduction”. This algorithm does not preserve the GCD and its related GCD algorithm has an O(n²) time bit complexity in the worst case. We present a modified version which avoids this problem. We show that a slightly modified GCD algorithm has an O(n²/logn) running time in the worst case, where n is the number of bits of the larger input.     

Comments on Samal and Henderson: “Parallel consistent labeling algorithms”

Samal and Henderson claim that any parallel algorithm for enforcing arc consistency in the worst case must have (na) sequential steps, wheren is the number of nodes, anda is the number of labels per node. We argue that Samal and Henderson's argument makes assumptions about how processors are used and give a counterexample that enforces arc consistency in a constant number of steps usingO(n[su2a²2^na) processors. It is possible that the lower bound holds for a polynomial number of processors; if such a lower bound were to be proven it would answer an important open question in theoretical computer science concerning the relation between the complexity classesP andNC. The strongest existing lower bound for the arc consistency problem states that it cannot be solved in polynomial log time unlessP=NC.     

A unifying approach for a class of problems in the computational geometry of polygons

A generalized problem is defined in terms of functions on sets and illustrated in terms of the computational geometry of simple planar polygons. Although its apparent time complexity is O(n ²), the problem is shown to be solvable for several cases of interest (maximum and minimum distance, intersection detection and rerporting) in O(n logn), O(n) or O(logn) time, depending on the nature of a specialized selection function. (Some of the cases can also be solved by the Voronoi diagram method; but time complexity increases with that approach.) A new use of monotonicity and a new concept of locality in set mappings contribute significantly to the derivation of the results.     

Optimal computation of prefix sums on a binary tree of processors

Givenn numbersa ₀,a ₁,...,a _n –1, it is required to compute all sums of the forma ₀+a ₁+...+a _i , fori=0, 1,...,n–1. This problem arises in many applications and is trivial to solve sequentially in O(n) time. Besides its practical importance, the problem gains an additional theoretical interest in parallel computation. A technique known asrecursive doubling allows all sums to be computed in O(logn) time on a model of computation wheren processors communicate through aninverse perfect suffle interconnection network. In this paper we show how the problem can be solved on a simple network, namely abinary tree of processors. In addition, we show how to extend our solution to obtain an optimal-cost algorithm. The algorithm usesp processors and runs in O((n/p)+logp) time, for a cost of O(n+p logp). This cost is optimal whenp logp=O(n). Finally, two applications of our results are illustrated, namely job scheduling with deadlines and the knapsack problem.This work was supported by the Natural Sciences and Engineering Research Council of Canada under Grants A0282 and A3336.     

Constant-time hough transform on the processor arrays with reconfigurable bus systems

We develop constant-time algorithms to compute the Hough transform on a processor array with a reconfigurable bus system (abbreviated to PARBS). The PARBS is a comptuation model which consists of a processor array and a reconfigurable bus system. It is a very powerful computation model in that many problems can be solved efficiently. In this paper, we introduce the concept of iterative-PARBS which is similar to the FOR-loop construct in sequential programming languages. The iterative-PARBS is a building block in which the processing data can be routed through it several times. We can think it as a “hardware subroutine”. Based on this scheme, we are able to explore constant-time Hough transform algorithms on PARBS. The following new results are derived in this study:

1. The sum ofn bits can be computed in O(1) times on a PARBS with O(n ^1+?) processors for any fixed ?>0.
2. The weights of each simple path of ann*n image can be computed in O(1) time on a 3-D PARBS with O(n ^2+?) processors for any fixed ?>0.
3. Thep angle Hough transform of ann*n image can be computed in O(1) time on a PARBS with O(p*n ^2+?) processors for any fixed ?>0 withp copies of the image pretiled.
4. Thep angle Hough transform of ann*n image can be computed in O(1) time on a PARBS with O(p*n ³) processors.

     

Towards separating nondeterminism from determinism

The main result of this paper is a separation result: there is a positive integerk such that for all well-behaving functionst(n), there is a language accepted by a nondeterministic (multi-tape) Turing machine in timet(n) which cannot be accepting by any deterministic (multitape) Turing machine in timeO(t(n)) and simultaneously spaceo((t(n)) ^1/k ). This implies, for example that for any positive integer,l,l k, there is a language accepted by an ^l time bounded NDTM which cannot be accepted by a DTM in time and spaceO(n ^l ) andO((logn) ^l ) respectively for anyl. Such a result is not provable by direct diagonalization because we do not have time to simulate and do the opposite". We devise a different method for accomplishing the result: We first use an alternating Turing machine to speed up the simulation of a time and space bounded DTM and then argue that if our separation result did not hold, every NDTM can itself be simulated faster by another NDTM producing a contradiction to the standard hierarchy results. Some other applications of this method are also presented.Supported by NSF Grant No. MCS-8105557     

The bottleneck k-MST

The k-MST is a well known NP-hard problem and several approximation algorithms exist to solve this problem with a guaranteed performance bound. A closely related problem, called the bottleneck k-MST (BMST(k)) can however be solved in O(mlogn) time on graph with n nodes and m edges. We propose two algorithms to solve BMST(k), one of complexity O(m+nlogn) and the other of O(m) time. We also consider a generalization of BMST(k) which subsumes many bottleneck problems studied in the literature and show that this generalized problem can also be solved in O(m) time.     

A Coarse-Grained Parallel Algorithm for the All-Substrings Longest Common Subsequence Problem

Given two strings A and B of lengths n_a and n_b, respectively, the All-substrings Longest Common Subsequence (ALCS) problem obtains, for any substring B' of B, the length of the longest string that is a subsequence of both A and B'. The sequential algorithm for this problem takes O(n_a n_b) time and O(n_b) space. We present a parallel algorithm for the ALCS problem on the Coarse-Grained Multicomputer (BSP/CGM) model with p < √n_a processors, that takes O(n_a n_b/p) time, O(log p) communication rounds and O(n_b √n_a) space per processor. The proposed algorithm also solves the basic Longest Common Subsequence (LCS) problem that finds the longest string (and not only its length) that is a subsequence of both A and B. To our knowledge, this is the best BSP/CGM algorithm in the literature for the LCS and ALCS problems.     

A unifying approach for a class of problems in the computational geometry of polygons

A generalized problem is defined in terms of functions on sets and illustrated in terms of the computational geometry of simple planar polygons. Although its apparent time complexity is O(n ²), the problem is shown to be solvable for several cases of interest (maximum and minimum distance, intersection detection and rerporting) in O(n logn), O(n) or O(logn) time, depending on the nature of a specialized “selection” function. (Some of the cases can also be solved by the Voronoi diagram method; but time complexity increases with that approach.) A new use of monotonicity and a new concept of “locality” in set mappings contribute significantly to the derivation of the results.