undefined | Better HN

0 pointsevrydayhustling1y ago0 comments

Nope, finite number of pieces and finite number of viable moves to check on each. Not sure what you're thinking of, but the entire concept of complexity class only applies if there is some axis of scaling (n-size chess board?).

0 comments

jdthedisciple1y ago

I think you might be misunderstanding:

Yes the instance of chess is finite but the problem of computing moves is inherently in NP.

The key is that just because a problem is in NP it does't mean that its difficult to solve the instances with small parameters.

See the famous coloring, SAT, or any other equal NP problem...

evrydayhustlingOP1y ago

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?

jdthedisciple1y ago

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.

j / k navigate · click thread line to collapse

0 comments

jdthedisciple1y ago

I think you might be misunderstanding:

Yes the instance of chess is finite but the problem of computing moves is inherently in NP.

The key is that just because a problem is in NP it does't mean that its difficult to solve the instances with small parameters.

See the famous coloring, SAT, or any other equal NP problem...

evrydayhustlingOP1y ago

jdthedisciple1y ago

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.

j / k navigate · click thread line to collapse