Path finding in the tile assembly model

Swarm robotics, active self-assembly, and amorphous computing are fields that focus on designing systems of large numbers of small, simple components that can cooperate to complete complex tasks. Many of these systems are inspired by biological systems, and all attempt to use the simplest components and environments possible, while still being capable of achieving their goals. The canonical problems for such biologically-inspired systems are shape assembly and path finding. In this paper, we demonstrate path finding in the well-studied tile assembly model, a model of molecular self-assembly that is strictly simpler than other biologically-inspired models. As in related work, our systems function in the presence of obstacles and can be made fault-tolerant. The path-finding systems use Θ(1)$\Theta \left(1\right)$ distinct components and find minimal-length paths in time linear in the length of the path.     

Nondeterministic polynomial time factoring in the tile assembly model

Formalized study of self-assembly has led to the definition of the tile assembly model, Previously I presented ways to compute arithmetic functions, such as addition and multiplication, in the tile assembly model: a highly distributed parallel model of computation that may be implemented using molecules or a large computer network such as the Internet. Here, I present tile assembly model systems that factor numbers nondeterministically using Θ(1)$\Theta \left(1\right)$ distinct components. The computation takes advantage of nondeterminism, but theoretically, each of the nondeterministic paths is executed in parallel, yielding the solution in time linear in the size of the input, with high probability. I describe mechanisms for finding the successful solutions among the many parallel executions and explore bounds on the probability of such a nondeterministic system succeeding and prove that the probability can be made arbitrarily close to 1.     

The effect of malformed tiles on tile assemblies within the kinetic tile assembly model

Many different constructions of proofreading tile sets have been proposed in the literature to reduce the effect of deviations from ideal behaviour of the dynamics of the molecular tile self-assembly process. In this paper, we consider the effect on the tile assembly process of a different kind of non-ideality, namely, imperfections in the tiles themselves. We assume a scenario in which some small proportion of the tiles in a tile set are “malformed”. We study, through simulations, the effect of such malformed tiles on the self-assembly process within the kinetic Tile Assembly Model (kTAM). Our simulation results show that some tile set constructions show greater error-resilience in the presence of malformed tiles than others. For example, the 2- and 3-way overlay compact proofreading tile sets of Reif et al. (DNA Computing 10, Lecture Notes in Computer Science, vol 3384. Springer, 2005) are able to handle malformed tiles quite well. On the other hand, the snaked proofreading tile set of Chen and Goel (DNA Computing 10, Lecture Notes in Computer Science, vol 3384. Springer, 2005) fails to form even moderately sized tile assemblies when malformed tiles are present. We show how the Chen–Goel construction may be modified to yield new snaked proofreading tile sets that are resilient not only to errors intrinsic to the assembly process, but also to errors caused by malformed tiles.     

Arithmetic computation in the tile assembly model: Addition and multiplication

Formalized study of self-assembly has led to the definition of the tile assembly model [Erik Winfree, Algorithmic self-assembly of DNA, Ph.D. Thesis, Caltech, Pasadena, CA, June 1998; Paul Rothemund, Erik Winfree, The program-size complexity of self-assembled squares, in: ACM Symposium on Theory of Computing, STOC02, Montreal, Quebec, Canada, 2001, pp. 459–468]. Research has identified two issues at the heart of self-assembling systems: the number of steps it takes for an assembly to complete, assuming maximum parallelism, and the minimal number of tiles necessary to assemble a shape. In this paper, I define the notion of a tile assembly system that computes a function, and tackle these issues for systems that compute the sum and product of two numbers. I demonstrate constructions of such systems with optimal Θ(1)$\Theta \left(1\right)$ distinct tile types and prove the assembly time is linear in the size of the input.     

Approximating MIN 2-SAT and MIN 3-SAT

We obtain substantially improved approximation algorithms for the MIN k-SAT problem, for k = 2,3. More specifically, we obtain a 1.1037-approximation algorithm for the MIN 2-SAT problem, improving a previous 1.5-approximation algorithm, and a 1.2136-approximation algorithm for the MIN 3-SAT problem, improving a previous 1.75-approximation algorithm for the problem. These results are obtained by adapting techniques that were previously used to obtain approximation algorithms for the MAX k-SAT problem. We also obtain some hardness of approximation results.     

Improving exact algorithms for MAX-2-SAT

We study three new techniques that will speed up the branch-and-bound algorithm for the MAX-2-SAT problem: The first technique is a group of new lower bound functions for the algorithm and we show that these functions are admissible and consistently better than other known lower bound functions. The other two techniques are based on the strongly connected components of the implication graph of a 2CNF formula: One uses the graph to simplify the formula and the other uses the graph to design a new variable ordering. The experiments show that the simplification can reduce the size of the input substantially no matter what is the clause-to-variable ratio and that the new variable ordering performs much better when the clause-to-variable ratio is less than 2. A direct outcome of this research is a high-performance implementation of an exact algorithm for MAX-2-SAT which outperforms any implementation we know about in the same category. We also show that our implementation is a feasible and effective tool to solve large instances of the Max-Cut problem in graph theory.Preliminary results of this paper appeared in [20,21]. This research was supported in part by NSF under grant CCR-0098093.     

Molecular solutions for minimum and exact cover problems in the tile assembly model

The tile assembly model is a novel biological computing model where information is encoded in DNA tiles. It is an efficient way to solve NP-complete problems due to its scalability and parallelism. In this paper, we apply the tile assembly model to solve the minimum and exact set cover problems, which are well-known NP-complete problems. To solve the minimum set cover problem, we design a MinSetCover system composed of three parts, i.e., the seed configuration subsystem, the nondeterministic choice subsystem, and the detection subsystem. Moreover, we improve the MinSetCover system and propose a MinExactSetCover system for solving the problem of exact cover by 3-sets. Finally we analyze the computation complexity and perform a simulation experiment to verify the effectiveness and correctness of the proposed systems.     

A molecular solution for minimum vertex cover problem in tile assembly model

Self-assembly is a generalization of the crystal growth, which has been proposed as a mechanism for the bottom-up fabrication of autonomous DNA computation. In the same context, tile assembly model is a highly distributed parallel model of natural self-assembly. In this paper, we propose a tile assembly system to tackle a well-known NP-complete problem known as Minimum Vertex Cover problem. The proposed algorithm requires Θ(n×m) types of tiles, and each parallel assembly executes in a linear time, where n is the number of vertices and m is the number of edges. Furthermore, the experimental results proved the simplicity and the efficiency of the proposed algorithm to solve the Minimum Vertex Cover, and reduce the overall complexity to find the solution.     

Step-wise tile assembly with a constant number of tile types

In this paper, we study the step-wise tile assembly model introduced by Reif (in: Based computers III, vol 48 of DIMACS, 1999) in which shape is assembled in multiple steps. In each step the partially built structure is exposed to a new set of tiles. We show that an N?×?N square can be assembled in N steps using a constant number of tile types. In general, we show that a constant number of tile types (24) is sufficient to assemble a large class of shapes in n steps, where n is the number of tiles of the shape. This class includes all shapes obtained from any shape by scaling by a factor of 2, in which case only 14 tile types suffices. For general shapes, we show that the tile complexity of this model is related to the monotone connected node search number of a spanning tree of the shape assuming the number of steps is n.     

Randomized Algorithms for 3-SAT

Schoning proposed a simple yet efficient randomized algorithm for solving the k-SAT problem. In the case of 3-SAT, the algorithm has an expected running time of poly(n)·(4/3)ⁿ = O(1.334ⁿ). In this paper we present randomized algorithms and show that one of them has O(1.3302ⁿ) expected running time, improving Schoning's algorithm. (Note. At this point, the fastest randomized algorithm for 3-SAT is the one given by Iwama and Tamaki that runs in O(1.324ⁿ).)     

Derandomizing the HSSW Algorithm for 3-SAT

We present a (full) derandomization of HSSW algorithm for 3-SAT, proposed by Hofmeister, Schöning, Schuler, and Watanabe (in STACS 2002, pp. 192–202, 2002). Thereby, we obtain an O(1.3303 ⁿ )-time deterministic algorithm for 3-SAT, which is currently fastest.     

Genetic algorithms for sequencing problems in mixed model assembly lines

Mixed model assembly lines are a type of production line where a variety of product models similar in product characteristics are assembled. The effective utilisation of these lines requires that a schedule for assembling the different products be determined. In this paper, the performance of genetic algorithms for sequencing problems in mixed model assembly lines is investigated. The problem first considered is a comparison between a existing heuristic and the proposed genetic algorithm to get the constant usage of every part used by the line considering variation at multi levels (Number of levels fixed as four. level 1—product, level 2—subassembly, level 3—component, level 4—raw-materials) for various test-bed problems. The algorithms proposed by Miltenburg and Sinnamon hereafter referred to as MS 1992 [IIE Trans. 24 (1992) 121] and the proposed genetic algorithm (GA) applied to mixed model assembly line are compared. Results of evaluation indicate that the GA performs better over MS1992 on 25 of the 40 problems investigated.

The other problem solved is a multiple objective sequencing problem in mixed model assembly lines. Three practically important objectives are minimizing total utility work keeping a constant rate of part-usage, minimizing the variability in parts usage and minimizing total setup cost. In this paper, the performance of the selection mechanisms, the Pareto stratum-niche cubicle and the selection based on scalar fitness function value are compared with respect to the objective of minimising variation in part-usage, minimising total utility work and minimising the setup cost. Results of evaluation indicate that the genetic algorithm that uses the Pareto stratum-niche cubicle performs better than the genetic algorithm with the other selection mechanisms.     

Quantum cooperative search algorithm for 3-SAT

Grover's search algorithm, one of the most popular quantum algorithms, provides a good solution to solve NP complexity problems, but requires a large number of quantum bits (qubits) for its functionality. In this paper, a novel algorithm called quantum cooperative search is proposed to make Grover's search algorithm work on 3-SAT problems with a small number of qubits. The proposed algorithm replaces some qubits with classical bits and finds assignments to these classical bits using the traditional 3-SAT algorithms including evolutionary algorithms and heuristic local search algorithms. In addition, the optimal configuration of the proposed algorithm is suggested by mathematical analysis. The experimental results show that the quantum cooperative search algorithm composed by Grover's search and heuristic local search performs better than other pure traditional 3-SAT algorithms in most cases. The mathematical analysis of the appropriate number of qubits is also verified by the experiments.     

Efficient algorithms for (3, 1) graphs

In this paper, we define a class of graphs which are referred to as (3, 1) graphs. A graph is a member of this class if it has the property that within each set of three vertices, there is at least one edge. We derive a lower bound for the size of a maximum clique in a (3, 1) graph as well as an upper bound for the size of a minimum clique covering. In addition, we show that there exists a linear algorithm for constructing a Hamiltonian circuit in a connected (3, 1) graph and an n⁴-algorithm for finding a minimum coloring in a (3, 1) graph.     

Random 3-SAT: The Plot Thickens

This paper presents an experimental investigation of the following questions: how does the average-case complexity of random 3-SAT, understood as a function of the order (number of variables) for fixed density (ratio of number of clauses to order) instances, depend on the density? Is there a phase transition in which the complexity shifts from polynomial to exponential in the order? Is the transition dependent or independent of the solver? Our experiment design uses three complete SAT solvers embodying different algorithms: GRASP, CPLEX, and CUDD. We observe new phase transitions for all three solvers, where the median running time shifts from polynomial in the order to exponential. The location of the phase transition appears to be solver-dependent. GRASP shifts from polynomial to exponential complexity near the density of 3.8, CPLEX shifts near density 3, while CUDD exhibits this transition between densities of 0.1 and 0.5. This experimental result underscores the dependence between the solver and the complexity phase transition, and challenges the widely held belief that random 3-SAT exhibits a phase transition in computational complexity very close to the crossover point.     

Self assembly of rectangular shapes on concentration programming and probabilistic tile assembly models

Efficient tile sets for self assembling rectilinear shapes is of critical importance in algorithmic self assembly. A lower bound on the tile complexity of any deterministic self assembly system for an n?×?n square is $\Upomega(\frac{\log(n)}{\log(\log(n))})$ (inferred from the Kolmogrov complexity). Deterministic self assembly systems with an optimal tile complexity have been designed for squares and related shapes in the past. However designing $\Uptheta(\frac{\log(n)}{\log(\log(n))})$ unique tiles specific to a shape is still an intensive task in the laboratory. On the other hand copies of a tile can be made rapidly using PCR (polymerase chain reaction) experiments. This led to the study of self assembly on tile concentration programming models. We present two major results in this paper on the concentration programming model. First we show how to self assemble rectangles with a fixed aspect ratio (??:??), with high probability, using $\Uptheta(\alpha+\beta)$ tiles. This result is much stronger than the existing results by Kao et?al. (Randomized self-assembly for approximate shapes, LNCS, vol 5125. Springer, Heidelberg, 2008) and Doty (Randomized self-assembly for exact shapes. In: proceedings of the 50th annual IEEE symposium on foundations of computer science (FOCS), IEEE, Atlanta. pp 85?C94, 2009)??which can only self assembly squares and rely on tiles which perform binary arithmetic. On the other hand, our result is based on a technique called staircase sampling. This technique eliminates the need for sub-tiles which perform binary arithmetic, reduces the constant in the asymptotic bound, and eliminates the need for approximate frames (Kao et?al. Randomized self-assembly for approximate shapes, LNCS, vol 5125. Springer, Heidelberg, 2008) . Our second result applies staircase sampling on the equimolar concentration programming model (The tile complexity of linear assemblies. In: proceedings of the 36th international colloquium automata, languages and programming: Part I on ICALP ??09, Springer-Verlag, pp 235?C253, 2009), to self assemble rectangles (of fixed aspect ratio) with high probability. The tile complexity of our algorithm is $\Uptheta(\log(n))$ and is optimal on the probabilistic tile assembly model (PTAM)??n being an upper bound on the dimensions of a rectangle.     

一种求解3-SAT问题的新方法

可满足性问题(SatisfiabilityProblem,SAT)是计算科学的典型问题之一,目前有DP算法、SAT1.3算法和遗传算法等多种求解方法。文章根据Kennedy和Eberhart提出的二进制粒子群优化算法(BinaryParticleSwarmOptimizers),基于局部随机搜索策略,给出了一种求解3-SAT问题的新方法:基于局部随机搜索的改进二进制粒子群优化算法(ModifedBinaryParticleSwarmOptimizersBasedonlocalstochasticsearch,简称MBPSO)。数值实验表明,对于随机产生的3-SAT问题测试实例,该算法是一种高效实用的新方法。