[evrydayhustling]

When we talk about what class a problem belongs in, we have to define the problem with respect to some scaling axis. For example, coloring with K=3 colors is NP-complete with respect to N = # nodes in the graph, but not with fixed N and scaling K. But I think it would actually be an interesting and non-trivial exercise to define a variant of chess with a scaling axis such that computing a list of valid moves for one player is NP-complete. Just scaling board size won't do it. Any suggestions?

[jdthedisciple]

Sorry I think I was talking about a different thing. With depth as scaling axis it should be NP-complete, but not with depth=1 which is what was being talked about. My bad.