Difference between revisions of "NP Hard Problems"
| Line 9: | Line 9: | ||
Tile assembly systems have been used to model solutions to NP complete problems, such as the subset sum problem. The subset sum problem asks if given a set of integers, is there a non-empty subset that sums to a precise number. | Tile assembly systems have been used to model solutions to NP complete problems, such as the subset sum problem. The subset sum problem asks if given a set of integers, is there a non-empty subset that sums to a precise number. | ||
| − | A proposed solution to the subset sum problem by <ref name=NPcomplete/> is to create a tile assembly system that subtracts numbers in the set $\overrightarrow{B}$ from the precise number \ | + | A proposed solution to the subset sum problem by <ref name=NPcomplete/> is to create a tile assembly system that subtracts numbers in the set $\overrightarrow{B}$ from the precise number $\mathit{v}$, non-deterministically guessing whether the next number $B_{i}$ should be subtracted. The number $B_{i}$ should be subtracted from $\mathit{v}$ only if $B_{i}$ is less than $\mathit{v}$. If it is not, $\mathit{v}$ should be copied until the next number $B_{i}$ is reached. If some subset of the numbers in the set $\overrightarrow{B}$ sum to $\mathit{v}$, then the $\mathit{v}$ should be 0 after all numbers in the subset have been subtracted. An identifier tile that can only attach to the configuration under those circumstances is used to find successful solutions more quickly. The implementation of this tile assembly can be accomplished at temperature 2 using 49 computation tiles and 7 seed tiles<ref name=NPcomplete/>. |
However, using tile assembly systems to solve NP problems is not practical. For a modest solution, an infeasible amount of space and materials is needed due to the necessity of parallel implementation and the exponential nature of NP problems. This limit on computational modeling cannot be overcome by molecular computing <ref name=infeasible/>. | However, using tile assembly systems to solve NP problems is not practical. For a modest solution, an infeasible amount of space and materials is needed due to the necessity of parallel implementation and the exponential nature of NP problems. This limit on computational modeling cannot be overcome by molecular computing <ref name=infeasible/>. | ||
Latest revision as of 14:22, 17 June 2019
NP (non-deterministic polynomial time) hard problems are those that all NP problems can be reduced to in polynomial time, so a polynomial solution to a NP hard problem could be used to solve NP problems in polynomial time. NP hard problems don’t have to be in NP, which is to say solutions to NP hard problems don’t have to be verifiable in polynomial time.
NP complete problems are NP problems that any other NP problem can be reduced to in polynomial time and whose solution can be verified in polynomial time. If a fast solution (polynomial time solution) can be found for any NP complete problem, then P = NP. In other words, if problems can be verified in polynomial time, they can be solved in polynomial time. NP hard problems can only be solved in polynomial time if P = NP. However, while not proven, it is speculated that P ≠ NP. This would mean there are NP problems that cannot be computed in polynomial time but can be verified in polynomial time.
Tile Assembly Solutions and Limitations
Tile assembly systems have been used to model solutions to NP complete problems, such as the subset sum problem. The subset sum problem asks if given a set of integers, is there a non-empty subset that sums to a precise number.
A proposed solution to the subset sum problem by [1] is to create a tile assembly system that subtracts numbers in the set \(\overrightarrow{B}\) from the precise number \(\mathit{v}\), non-deterministically guessing whether the next number \(B_{i}\) should be subtracted. The number \(B_{i}\) should be subtracted from \(\mathit{v}\) only if \(B_{i}\) is less than \(\mathit{v}\). If it is not, \(\mathit{v}\) should be copied until the next number \(B_{i}\) is reached. If some subset of the numbers in the set \(\overrightarrow{B}\) sum to \(\mathit{v}\), then the \(\mathit{v}\) should be 0 after all numbers in the subset have been subtracted. An identifier tile that can only attach to the configuration under those circumstances is used to find successful solutions more quickly. The implementation of this tile assembly can be accomplished at temperature 2 using 49 computation tiles and 7 seed tiles[1].
However, using tile assembly systems to solve NP problems is not practical. For a modest solution, an infeasible amount of space and materials is needed due to the necessity of parallel implementation and the exponential nature of NP problems. This limit on computational modeling cannot be overcome by molecular computing [2].
References
- ↑ 1.0 1.1
Yuriy Brun - Solving NP-Complete Problems in the Tile Assembly Model
- Theoretical Computer Science pp. 31-46,2008
- BibtexAuthor : Yuriy Brun
Title : Solving NP-Complete Problems in the Tile Assembly Model
In : Theoretical Computer Science -
Address :
Date : 2008
- ↑
David Doty - Theory of Algorithmic Self-Assembly
- Communications of the ACM pp. 80-81,2012
- BibtexAuthor : David Doty
Title : Theory of Algorithmic Self-Assembly
In : Communications of the ACM -
Address :
Date : 2012
