我怀疑你理解有误.

> 围棋被证明属于 EXPTIME-complete 问题
这是对的
但这里的围棋不是我们生活中的19x19的围棋, 而是数学意义的通用围棋.
O(2 poly(n) ) 里的N 指的是棋盘的大小.

我们生活中的围棋当然是NP完全问题,  O(2 poly(n) ); n=19,
虽然数字很大, 但是确定的.

=========
所以你的回复跟楼主所说的围棋是两码事



【 在 zszqzzzf 的大作中提到: 】
: 围棋问题，难在比NP完全问题难。
: 围棋被证明属于 EXPTIME-complete 问题（指数时间完成），即最优策略求解需指数级时间 O(2 poly(n) )。
: 与NP的关系：EXPTIME完全问题比NP完全问题更难（因 NP被包含于EXPTIME），且已证明 P<>EXPTIME，故围棋不可能存在多项式时间解法。
: ...................
--
FROM 221.216.136.*