Arrow Research search

Author name cluster

Leonard M. Adleman

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

21 papers
2 author rows

Possible papers

21

FOCS Conference 2002 Conference Paper

On the Decidability of Self-Assembly of Infinite Ribbons

  • Leonard M. Adleman
  • Jarkko Kari 0001
  • Lila Kari
  • Dustin Reishus

Self-assembly, the process by which objects autonomously come together to form complex structures, is omnipresent in the physical world. A systematic study of self-assembly as a mathematical process has been initiated. The individual components are modelled as square tiles on the infinite two-dimensional plane. Each side of a tile is covered by a specific "glue", and two adjacent tiles will stick if they have matching glues on their abutting edges. Tiles that stick to each other may form various two-dimensional "structures" such as squares, rectangles, or may cover the entire plane. In this paper we focus on a special type of structure, called ribbon: a non-self-crossing sequence of tiles on the plane, in which successive tiles are adjacent along an edge, and abutting edges of consecutive tiles have matching glues. We prove that it is undecidable whether an arbitrary finite set of tiles with glues (infinite supply of each tile type available) can be used to assemble an infinite ribbon. The proof is based on a construction, due to Robinson (1971), of a special set of tiles that allow only aperiodic tilings of the plane. This construction is used to create a special set of directed tiles (tiles with arrows painted on the top) with the "strong plane filling property" - a variation of the "plane filling property" previously defined by Kari (1990, 1994). A construction of "sandwich" tiles is then used in conjunction with this special tile set, to reduce the well-known undecidable tiling problem to the problem of the existence of an infinite directed zipper (a special kind of ribbon). A "motif" construction is then introduced that allows one tile system to simulate another by using geometry to represent glues. Using motifs, the infinite directed zipper problem is reduced to the infinite ribbon problem, proving the latter undecidable. The result settles an open problem formerly known as the "unlimited infinite snake problem". Moreover, an immediate consequence is the undecidability of the existence of arbitrarily large structures self-assembled using tiles from a given tile set.

Details

FOCS Conference 1994 Conference Paper

Algorithmic Number Theory-The Complexity Contribution

  • Leonard M. Adleman

Though algorithmic number theory is one of man's oldest intellectual pursuits, its current vitality is perhaps unrivalled in history. This is due in part to the injection of new ideas from computational complexity. In this paper, a brief history of the symbiotic relationship between number theory and complexity theory will be presented. In addition, some of the technical aspects underlying 'modern' methods of primality testing and factoring will be described. Finally, an extensive lists of open problems in algorithmic number theory will be provided. >

Details

FOCS Conference 1982 Conference Paper

An Application of Higher Reciprocity to Computational Number Theory (Abstract)

  • Leonard M. Adleman
  • Robert McDonnell

The Higher Reciprocity Laws are considered to be among the deepest and most fundamental results in number theory. Yet, they have until recently played no part in number theoretic algorithms. In this paper we explore the power of the laws in algorithms. The problem we consider is part of a group of well-studied problems about roots in finite fields and rings. Let F denote a finite field, let m denote a direct product of finite fields. Consider the following problems: Problem 1. Is Xn = a solvable in F; Problem 2. If Xn = a is solvable in F find X; Problem 3. Is Xn = a solvable in m; Problem 4. If Xn = a solvable in m find X.

Details

FOCS Conference 1980 Conference Paper

On Distinguishing Prime Numbers from Composite Numbers (Abstract)

  • Leonard M. Adleman

A new algorithm for testing primality is presented. The algorithm is distinguishable from the lovely algorithms of Solvay and Strassen [36], Miller [27] and Rabin [32] in that its assertions of primality are certain (i. e. , provable from Peano's axioms) rather than dependent on unproven hypothesis (Miller) or probability (Solovay-Strassen, Rabin). An argument is presented which suggests that the algorithm runs within time c1ln(n)c2ln(ln(ln(n))) where n is the input, and C1, c2 constants independent of n. Unfortunately no rigorous proof of this running time is yet available.

Details

FOCS Conference 1979 Conference Paper

Reductions that Lie

  • Leonard M. Adleman
  • Kenneth L. Manders

All of the reductions currently used in complexity theory (≤p, ≤γ, ≤R) have the property that they are honest. If A ≤ B then whatever machine M reduces A to B is such that: if on input x, M outputs y then x ε A ↔ y ε B. It would appear that this membership preserving property is intrinsic to the notion of reduction. We will see that it is not. We introduce reductions that lie and sometimes produce outputs y ε B when x? A. We will use these reductions to further clarify the computational complexity of some problems raised by Gauss.

Details