求问一道狗家np-hard题

经常看到有人被问到这个题 想请问一下大神们肿么做

设计一个np hard的迷宫

http://stackoverflow.com/questions/535859/non-exponential-solution-to-maze-problem        可以用3SAT问题进行规约。

xh_pku 发表于 2016-8-27 13:58
http://stackoverflow.com/questions/535859/non-exponential-solution-to-maze-problem        可以用3SAT ...

这个看过了 就是感觉有点牵强 可是其他的看着虽然更直观 要dress up to np hard有点难 比如三色格子擦掉浅蓝
http://gwydir.demon.co.uk/jo/maze/design/index.htm#puzzle

楼主后来想了想 估计题目的意思只是要做个np的maze 所以应该不需要dress up to sat之类的 只需要证明能在p的时间verify就行 这样应该容易多了吧 感觉。。