Methods for generating a distribution of optimal solutions to nondeterministic polynomial optimization problems

Abstract

The present invention provides methods for generating a distribution of optimal answers to a nondeterministic polynomial optimization problem by providing a plurality of solutions comprising input polynucleotides, wherein each solution comprises identical input polynucleotides; and wherein the number of solutions comprising polynucleotides equals a number of data inputs in the problem to be answered, and wherein each input polynucleotide comprises an x segment and a y segment; providing a plurality of solutions comprising connection polynucleotides wherein each solution comprises identical connection polynucleotides; and wherein the number of solutions comprising connection polynucleotides equals a number of unique connections that can be made between the different data inputs, and wherein each polynucleotide in the set of connection polynucleotides is complementary to the x segment of one input polynucleotide and to the y segment of one different input polynucleotide; combining the solutions comprising the input polynucleotides with the solutions comprising the connection polynucleotides to form a hybridization mixture, wherein the combining is done under conditions to promote formation of hybridization complexes between complementary polynucleotides, and wherein each individual connection polynucleotide is added at a concentration based on a weighted value assigned to the individual connection polynucleotide; ligating the polynucleotides that are present in the hybridization complexes to form ligation products; and determining a concentration of the ligation products, wherein the ligation products present at the highest concentration represent optimal answers to the nondeterministic polynomial optimization problem.