Solving NP-hard puzzles with Slime Molds (2025)
I had the pleasure of being able to do this project as SURA research with the university. A formal paper is in the works, but informally: I used Karp reductions to transform an instance of NP-hard problem Exact 3 Cover (X3C) to Euclidean Steiner Tree, which is a problem that Physarum Polycephalum is able to solve with 60% consistency. X3C is naturally able to encode problems such as Tiling and Sudoku (though the latter would be tremendously large) meaning I was affectively able to have Physarum Polycephalum take a stab at solving these problems. If you’re curious about how any of this works, please reach out, I love to talk about this kind of stuff.