NP Hard Problems

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 is to create a tile assembly system that subtracts numbers in the set \overrightarrow{B} from the precise number \textit{v}, non-deterministically guessing whether the next number \(B_{i}\) should be subtracted. The number \(B_{i}\) should be subtracted from \textit{v} only if \(B_{i}\) is less than \textit{v}. If it is not, \textit{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 \textit{v}, then the \textit{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.

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 .