3 ms·
Not sure if mazes are np complete but if so could we map other problems into maze designs and the water can solve problems for us?
by bilsbie 4y ago
Not sure if mazes are np complete but if so could we map other problems into maze designs and the water can solve problems for us?
- thih9 4y agoI thought we decided to use electricity and silicon mazes instead? But there were attempts to use water too, e.g. MONIAC: https://en.m.wikipedia.org/wiki/MONIAC https://en.m.wikipedia.org/wiki/MONIAC
- patates 4y agoIf you extend the definition of the maze a bit, aren't all circuits mazes? But then, you can keep extending it and say that everything is a computer and also a maze. Anyway, the brain gymnastics is a lot of fun, at least for me.
- xmcqdpt2 4y agoThey are not NP at all. A perfect maze (with one solution) as a connectivity graph is a tree. Finding the path through a tree can be done by DFS in linear O(N) time.
- brokensegue 4y agoall P problems are in NP \pedantic