DNAコンピュータで20変数の3SAT問題を解く

Ravinderjit S Braich¹, Nickolas Chelyapov, Cliff Johnson

¹University of Southern California, Laboratory for Molecular Science, Los Angeles, CA 90089-1340, USA.

Science (New York, N.Y.)

|March 16, 2002

まとめ

研究者はDNAコンピュータを使って20変数の複雑な問題を解き,100万以上の可能性を探求した. これは,生物学的手段で大規模な計算問題を解決する上で重要な進歩を示しています.

科学分野:

バイオコンピューティング
コンピューティングの複雑性理論
分子コンピューティング

背景:

3つの満足度 (3-SAT) 問題は,コンピュータサイエンスの基本的なNP完全問題である.
3-SATの大きなインスタンスを解決することは,従来の電子コンピュータにとって計算的に困難です.

研究の目的:

複雑な計算問題を解くための単純なDNAコンピュータの能力を実証するために.
大規模な計算のために生物学的分子を使用する可能性を調査する.

主な方法:

3SAT問題の20変数のインスタンスが,DNAベースの計算アプローチを使用してコード化され,解決されました.
DNAコンピュータは,ユニークな解決策を見つけるために100万 (2^20) 以上の可能性を徹底的に検索しました.

主要な成果:

DNAコンピュータは,20変数の3SAT問題に対するユニークな解決策を成功裏に特定しました.
これは,非電子的,生物学的方法を使用してこれまでに解決された最大の計算問題の一つを表しています.

結論:

DNAコンピューティングは,コンピューティングに密集した問題に取り組むための実行可能な代替案を提供します.
このソリューションの規模は,DNAコンピュータが人間や従来のコンピューティングの限界を超えた問題を解決する可能性を示唆しています.

さらに関連する動画

07:44

Design and Synthesis of a Reconfigurable DNA Accordion Rack

Published on: August 15, 2018

09:26

DNA-Tethered RNA Polymerase for Programmable In vitro Transcription and Molecular Computation

Published on: December 29, 2021

関連する概念動画

02:05

DNA as a Genetic Template

Two structural features of the DNA molecule provide a basis for the mechanisms of heredity: the four nucleotide bases and its double-stranded nature. The Watson-Crick model of double-helical DNA structure, proposed in 1952, drew heavily upon the X-ray crystallography work of researchers Rosalind Franklin and Maurice Wilkins. Watson, Crick, and Wilkins jointly received the Nobel Prize in Physiology or Medicine for their work in 1962. Franklin was, controversially, excluded from the prize for...

02:34

DNA Microarrays

Microarrays are high-throughput and relatively inexpensive assays that can be automated to analyze large quantities of data at a time. They are used in genome-wide studies to compare gene or protein expression under two varied conditions, such as healthy and diseased states. Microarrays consist of glass or silica slides on which probe molecules are covalently attached through surface functionalization. Most commonly, the slides are prepared through the chemisorption of silanes to silica...

02:05

DNA as a Genetic Template

01:16

Statically Indeterminate Problem Solving

Statically indeterminate problems are those where statics alone can not determine the internal forces or reactions. Consider a structure comprising two cylindrical rods made of steel and brass. These rods are joined at point B and restrained by rigid supports at points A and C. Now, the reactions at points A and C and the deflection at point B are to be determined. This rod structure is classified as statically indeterminate as the structure has more supports than are necessary for maintaining...

01:14

Castigliano's Theorem: Problem Solving

The deflection of a simply supported beam that carries a central point load can be analyzed using structural mechanics principles, particularly by applying Castigliano's theorem. This theorem relates the displacement at the load application point to the partial derivatives of the strain energy in the structure. The simply supported beam with a point load at its center has symmetric reaction forces at the supports, each bearing half of the load. The bending moment at any point along the beam is...

01:31

Functions of Three or More Variables

A function of three variables assigns a single real number to each point in three-dimensional space. Every point is identified by its Cartesian coordinates, x, y, and z, and the function maps this ordered triple to a scalar value. Such functions are commonly used to describe physical quantities that vary throughout space.A representative example is the electric potential generated by a point charge. In this case, the potential at a given location depends only on the distance from the charge. If...

関連する実験動画