VC 與 AOC

前幾天看到 matrix67 的 blog, 覺得很有趣, 便一直在想除了還有沒有其它做法
由於沒有打 SC (StarCraft), 不過應該和 AOC 差不多 (其實這些即時戰略遊戲應該都不大差別)
即是說, 給出一個 AOC 的局況, 判斷某一方是否能勝出

文中用的 NPC 問題是 PLANAR GRAPHS HAMILITON PATH, 把判斷 "圖 G 是否存在 HAMILITON PATH" 轉化成判斷 "此 SC 局況某方是否能勝出", 從而得出 SC 是 NP-HARD 的結論
類似的, 現在要選一個 NPC 問題, 把它轉化成 AOC 中的局況

想到的是 PLANAR GRAPHS VERTEX COVER
這個問題即使限制 degree 不大於 3 仍是 NPC 的 (見 Wikipedia)
即是說, 給出圖 G, 是否能選取不多於 k 個頂點覆蓋所有的邊

現假設有玩家 A 和 B
玩家 A 有 |E| 隻劍兵, 對應著 |E| 條邊, 而且是被困著的 (例如地圖是海, 劍兵在孤島)
玩家 B 則沒有村民和軍隊, 但有 |V| 座弓箭場 (在 |V| 個島上) 和剛好夠資源生產 k 隻茅兵

對於邊 (u, v), 要做到在島 u 生產的茅兵能射到這條邊的劍兵但又不能走到島 v
具體方法是



即是說, 在某個島生產茅兵能殺掉相鄰邊上的玩家 A 劍兵
玩家 B 能勝出的唯一方法是殺掉所有劍兵, 顯然的, 這對應著圖 G 有 size k 的 vertex cover
即是說, 如果懂得判定 AOC 的勝負問題, 則懂得判定 planar 的 VC 問題
得出 AOC 是 NP-HARD 的

ps0. 更多的遊戲
ps1. AOC 今年會更新! :D

ITCSC-INC Winter School 2012: Keywords

Network Coding
- Randomized coefficient matrix G: (i, j) : e[j] = G[i][j] * e[i]
- High Probability Det != 0
- Theorem: Cut(s, t) = Maximum information sent from s to t = #Linearly Independent vectors

Directed Graph connectivity
- F = H + GF, F = H * inv(I - G)
- High Probability: Min Cut = Matrix Rank
- Compute inv(I - G), Matrix for Cut(s, t) = extract submatrix from it

Single Source
- Topological sort, O(Δd²)
- Use Superconcentrators → O(Δd)

Expanders
- Sparse and highly connected
- Example: Bipartite Graph (n, 0.75n), left regular with constant number of edges
- High Probability: if |S| ≤ n/2 → |N(S)| ≥ |S|

Superconcentrators
- G(I, O): I, O = disjoint vertex sets
- For every k, choose k vertex from I, O and there exists k edge-disjoint path
- Construct: edge from I_i to O_i
- |I'| = 0.75|I|, |O'| = 0.75|O|, Expanders: (I, I'), (O', O)
- Recursively Superconcentrators G(I', O')

Matrix Rank
- Find linearly independent columns vectors for A_{m × n}
- Regular Bipartite Graph (n, 10m): left degree = 2, right degree = n/5m
- B[i] = Random Linear Combination of n/5m column vectors from A
- Done in O(#Non-zero entries in A)
- High Probability: Rank(B_{m × 10m}) = Rank(A_{m × n})
- Trace: at most n/5 vectors in A are candidate: reduce problem to A'_{m × n/5}

Sem 4 1/13: Begin

不知不覺間來到第 4 個 sem, 感覺還是一事無成
出了 GPA, 以數值來看總算可以很自然地告訴別人
該 A 的科都 A 了, A 不了的也沒有很失望

下年會不會去 exchange 還是未知數
今個 sem 還是讀書 + ACM (其實我都唔知仲可以有甚麼..)
繼續全部讀 major

CSC 310 - Software Engineering
十半堂當然不上, 也沒有一定要上的理由
為了吸引人答問題派 coupon ← dislike

CSC 318 - Principles of Programming Languages
感覺: 未讀過就唔叫讀過CS, 不過興趣不大

CSC 325 - Computers and Society
還在 waitlist, 計 attendance 的 tutorial 撞了 day-off, 極有可能 drop
不得不提這個 course = 浪費時間, 還要做 project, 莫明奇妙

CSC 342 - Computer Architecture
又是李健康, 又有 4 個 quiz + resubmit..
不過 project 用 C 做! 希望唔好咁痛苦..

CSC 443 - Data Communication and Computer Networks
mole神的 course! 由於 workload 很大所以沒有 take
不過如果不是很忙的話打算去 S 班食花生, 上 mole神堂學到很多野呢

CSC 506 - Topics in the theory of computing
被 chin 慫恿去上了一堂 Andrej 的 course, 感覺: 正
內容是 coding theory + boolean functions + expander
應該會繼續 sit 下去

CSC 516 - Spectrum Algorithms
這個 sem 最刺激的 course, 內容大部份都未聽過
據超超講 + 自己經驗: 每個星期要花數小時複習
目前感覺是 linear algebra 和 graph 的關係
未來幾個月應該要和 matrix 做朋友了

最後當然是 WF
不過感覺離 WF 還有很多時間, 又很久沒有 5hr 的 training, 完全未有應有的緊張感
目前還沒有一個很明確的 rank 目標, 所以還是專心做題目吧