1樓：好地方bug
瀉藥，可以從點覆蓋問題（Vertex Cover Problem）規約。我先形式化描述一下這兩個問題，為了規約方便，我們考慮支配集問題（Dominating Set Problem）的判定性版本。
Input：無向圖 和乙個正整數 。
Output：是否存在乙個大小不超過 的點子集 ，使得每條邊的兩個端點，至少有乙個在 中（即被端點覆蓋）。（我們稱 是大小不超過 的點覆蓋）
Input：無向圖 和乙個正整數 。
Output：是否存在乙個大小不超過 的點子集 ，使得 中的每個點，要麼在 中，要麼有個鄰居在 中（即被它鄰居支配）。（我們稱 是大小不超過 的支配集）
定理：Dominating Set Problem是NPC的。
證明：對於任意乙個Vertex Cover Problem的例項 ，我們構造乙個Dominating Set Problem的例項 ：
首先 是 的乙個複製，接下來對於 中的任意一條邊 ，我們在 中新增乙個點 ，並且新增邊 。
那麼我們可以斷言，如果 回答的是yes，當且僅當 回答的也是yes。
：考慮 的乙個大小不超過 的點覆蓋 ，顯然 也同樣是 的支配集，並且大小不超過 。
：考慮 的乙個大小不超過 的支配集 ，我們將 中那些不是 中的點，換到他的鄰居上，得到 （比如 ，那麼把 去掉，加入 或者 ）。由於 能支配的點， 也能支配，所以 依舊是個支配集，並且 只包含 中的點。
現在由於 中的點都被 支配了，所以在 中，每條邊都會被 覆蓋。所以 是大小不超過 的， 的點覆蓋。證畢。
如何證明 3 05 ？
拓跋景帆 解A.由 sin x x 0 eeimg 1 可得 sin frac frac 2 eeimg 1 於是 4 sqrt eeimg 1 只需證 61 eeimg 1 兩邊平方得 3721 eeimg 1 即 再平方就是 得證.解B.由 sin x x 0 eeimg 1 可得 sin fr...
如何證明 injectivity of type constructors
Anqur 這個問題好像少提供了一些 context,咱是故意的 隨便給個 context 讓它 hold 是可以的.最近在看 Jon Sterling 寫的材料,因為他,包括 Coquand 老爺等一批人這幾年在 CTT 幹的事情,其中的脈絡好像更清晰了 Taichi Uemura 的型別論新 c...
如何證明 1 1 4 1 9 1 16 1 25 6？
題主問題是Problems in Analytic Number Theory M.Ram Murty 習題5.5.5。放乙個有趣的小結論 這個二重和式可推廣成 比證明更重要的是怎麼去理解這個特殊的數！一種角度是Riemann 而這個和巧合就是 就是 function 的特殊值。 瑜書 前幾天思考另...