请问如何准确目算双方的实地?
NP-hardness与围棋---有关围棋必胜的计算量
不是所有的難題都可?w結??NP ??題,像下得一手絕?玫?瀣F在目前的推?y是比所有 NP ??題?要難的?算??題,即 NP-hard ??題,NP-hard ??題的定義如下:
定義: 若 x ?橐?NP-hard ??題,?t若 NP ,?t 。
也就是說,即使 P=NP,x ?不一定?凫?P,但 NP, ?t x 絕不比 NP 的??題容易。在第三?中的??題1、3不一定是 NP ??題,但若能以 O(nk) 的?算量解?Q它??,?t比較容易的??題2與4也可以 O(nk) 解?Q,故若??題1、3 ?t??題2、...全部
NP-hardness与围棋---有关围棋必胜的计算量
不是所有的難題都可?w結??NP ??題,像下得一手絕?玫?瀣F在目前的推?y是比所有 NP ??題?要難的?算??題,即 NP-hard ??題,NP-hard ??題的定義如下:
定義: 若 x ?橐?NP-hard ??題,?t若 NP ,?t 。
也就是說,即使 P=NP,x ?不一定?凫?P,但 NP, ?t x 絕不比 NP 的??題容易。在第三?中的??題1、3不一定是 NP ??題,但若能以 O(nk) 的?算量解?Q它??,?t比較容易的??題2與4也可以 O(nk) 解?Q,故若??題1、3 ?t??題2、4,又因2、4是 NP-complete,即推出 NP=P。
這與 NP-hard 之定義相合,故??題1、3均??NP-hard ??題。同理??題5也?凫?NP-hard,不過這些 NP-hard 似乎比 NP 難不了多少,但下棋??題可能比 NP ??題要難得多,???題可以作如下觀。
??題11。(???題)
以平常的?逡??t在一?? n x n 的棋盤上下,給定一????局(下了二??子就可以算??局),首先,是否可以確定黑子在最好的下法之下,一定?A?
這????題不能用一般的方法證明它是不是??NP。
因?槟壳?]有人能猜一??必?俚南路ㄇ以?O(np) ?r?茸C明它是?Φ模?樗c?Ψ饺绾?队嘘P,而?撤降?队峙c他?δ阋葬岬南路ǖ耐?y有關,如此往下走,首先發生困難的是???上亮了紅?簦此枰挠???可能呈方次以上的進展。
因每一?????至少要用(?碛?算)一次,否?t這?????就不如不要,因此一????題的???若呈指?瞪仙?t其?算量亦非呈指?邓频纳仙豢桑裟??題只需要方次上升的???,即不能保證它只需要方次上升的?算量。
因此?算?C?W家定義三??新的集合:
PSPACE={x:x 只需要方次上升的??? }
註:x 均指??題。
PSPACE-complete:
若 PSPACE,
又 PSPACE-complete,
且 ,
?t P= PSPACE。
PSPACE-hard:
若 PSPACE-hard,
且 ,
?t P= PSPACE。
注意在上式中 PSPACE-complete PSPACE,即 PSPACE-complete 是 PSPACE 中的難題,但 PSPACE-hard 不一定?凫?PSPACE。
Stockmeyer and Meyer 在1937年證明了一??與古克相似的定理。
若令 表示存在一?? x, 表?λ械?x,Q 表 , 中的一??,x ?椴际献???與1,?t我??稱 f(Q1 x1,Q2 x2,…,Qn xn) ?橐涣炕际瞎健H?f 有可能??,?t f 稱之?榭?M足,例如把第四?中之(1)式改??成
?t上式不可能?M足,因??(u3 ??0 或 1)而言,f 不全是1。
Stockmeyer 與 Meyer 之定理?椋?
定理:
?z定一??量化布氏公式?榭?M足是一?? PSPACE-complete ??題。
?我??下棋面?χ槐P??局沉思的?r候,我??的要求是
?ξ沂欠翊嬖谝恢?倨蹇梢?Ω?
?橙巳魏我恢?镀?
此後我是否存在一著必?倨蹇梢?Ω?
?橙巳魏我恢?镀?
……
我是否存在一著必?倨蹇梢?Ω?
?橙巳魏我恢?
我贏了
因此這完全是 ,,,,… 之交替作用與Stockmeyer 與 Meyer 定理之關?S至?槊芮校?Robertson 與 Munro 在1918年證得?迨且环N PSPACE-hard 的??題,目前有人?算到??8 必?俜ㄖ????算量在 10600 以上,不?人腦或?腦的???絕少不了一??原子,而現今所知的宇宙原子?导s只有 1075。
棋之道,大矣哉!要做一??下?灞?俚?C器人是?何容易!
。收起