Yes. But you don't need to keep the whole tree in memory. | Hacker News

Hacker Newsnew | past | comments | ask | show | jobs | submit

		eterevsky on May 25, 2023 \| parent \| context \| favorite \| on: Problems harder than NP-Complete Yes. But you don't need to keep the whole tree in memory.

kevinwang on May 25, 2023 [–]

Ahh sorry, I see what you're saying now. Yeah I guess it's in PSPACE if the length of each game is polynomial in n, and EXPTIME if games can go on for longer.

I guess chess (without the 50-move rule), checkers, and go (with a certain ruleset) can go on for longer.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact