Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

01.06.2015 | Ausgabe 2/2015

Natural Computing 2/2015

3-color bounded patterned self-assembly

Zeitschrift:
Natural Computing > Ausgabe 2/2015
Autoren:
Lila Kari, Steffen Kopecki, Shinnosuke Seki
Wichtige Hinweise
The research of L. K. and S. K. was supported by the NSERC Discovery Grant R2824A01 and UWO Faculty of Science grant to L. K. The research of S. S. was supported by the HIIT Pump Priming Project Grant 902184/T30606 and the Academy of Finland, Postdoctoral Researcher Grant 13266670/T30606.

Abstract

The problem of patterned self-assembly tile set synthesis (Pats) is to find a minimal tile set which uniquely self-assembles into a given pattern. Czeizler and Popa proved the \(\mathrm {NP}\)-completeness of Pats and Seki showed that the Pats problem is already \(\mathrm {NP}\)-complete for patterns with 60 colors. In search for the minimal number of colors such that Pats remains \(\mathrm {NP}\)-complete, we introduce multiple bound Pats (mbPats) where we allow bounds for the numbers of tile types of each color. We show that mbPats is \(\mathrm {NP}\)-complete for patterns with just three colors and, as a byproduct of this result, we also obtain a novel proof for the \(\mathrm {NP}\)-completeness of Pats which is more concise than the previous proofs.

Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 69.000 Bücher
  • über 500 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 50.000 Bücher
  • über 380 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Maschinenbau + Werkstoffe




Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Testen Sie jetzt 30 Tage kostenlos.

Literatur
Über diesen Artikel

Weitere Artikel der Ausgabe 2/2015

Natural Computing 2/2015 Zur Ausgabe

EditorialNotes

Preface

Premium Partner

    Bildnachweise