Hamiltonian Path Problem
William Rowan Hamilton studied mathematical problems on graphs in the 1800s. Computer scientists classify the Hamiltonian path problem as NP-complete—no known polynomial-time algorithm exists. Richard Karp included it among 21 NP-complete problems in his foundational 1972 paper. Computational complexity theorists study problem hardness. Researchers explore alternative computing paradigms—quantum, DNA, analog—potentially offering speedups.
Bacterial DNA Computing
Researchers demonstrated bacteria solving Hamiltonian path problems through DNA recombination and selection. Leonard Adleman pioneered DNA computing solving similar problems in test tubes. Synthetic biologists engineer bacterial computation circuits. Bioengineers explore living cells as programmable computers exploiting cellular machinery for information processing.
Massively Parallel Biological Computation
Leonard Adleman demonstrated DNA computing’s massive parallelism solving Hamiltonian path problems with trillions of DNA molecules working simultaneously. Researchers exploit bacterial exponential growth creating billions of parallel computers. Computer scientists study parallel algorithms and their biological implementations. Synthetic biologists engineer cellular computation exploiting population-level parallelism.