三十年懸案終解：二部圖匹配被證明屬於 NC 類
ECCC TR26-100 · 2026-06-14
2026 年 6 月 14 日，五位研究者在電子計算複雜度學報（ECCC）發表論文 TR26-100，正式證明二部圖最大匹配（bipartite matching）屬於複雜度類 NC——即可在多項式數量的平行處理器上、以多對數時間確定性地求解。Scott Aaronson 在部落格形容這是「一個真正美麗的結果」，並指出這個問題自 1980 年代就被提出，但長達四十年都只有隨機化解法。
原本的問題
NC（Nick's Class）是指能被高度平行化的問題集合，實務上相當於「可在合理時間內用大量處理器解決」。1986 年，Karp、Upfal、Wigderson 曾證明二部圖匹配可平行求解，但前提是處理器能存取隨機位元——即屬於 RNC 而非 NC。此後的去隨機化（derandomization）工作始終是理論電腦科學的公開難題。加權版本的匹配與符號矩陣的秩計算同樣懸而未決。
採用的方法
作者 Abhranil Chatterjee、Sumanta Ghosh、Rohit Gurjar、Roshan Raj、Thomas Thierauf 採用了多項式方法（polynomial method），靈感來自 Guruswami 與 Kopparty 在子空間設計（subspace design）的構造技巧。核心概念是建構「隔離引理（isolation lemma）」的確定性版本，使最小權重完美匹配在某個線性形式下唯一被識別，從而避免使用隨機性。論文於 6 月 15 日發布第一版修訂，修正 Theorem 5.2 的證明細節。
影響範圍
論文同時將結果延伸至加權二部圖匹配、符號矩陣的非交換秩（noncommutative rank of symbolic matrices），以及線性擬陣交集（linear matroid intersection）的決策版本，三者均一併納入 NC。二部圖匹配是排程、指派與最佳化問題的核心子程式，此結果在理論層面打開了一道門；不過從理論 NC 演算法到工程實用仍有距離，論文本身並未宣稱立即的實作效益。
原始來源：ECCC TR26-100；延伸閱讀：Scott Aaronson's Blog
在瀏覽器裡跑完整 LaTeX：SwiftLaTeX 把 PdfTeX 與 XeTeX 編譯成 WebAssembly
SwiftLaTeX / Hacker News 討論 · 2026-06-27
SwiftLaTeX 在 2026 年 6 月底重新引發社群關注，HN 討論串吸引逾 89 則留言。這個專案把 PdfTeX 與 XeTeX 完整編譯成 WebAssembly，讓瀏覽器頁面在本機執行 LaTeX，無需後端伺服器、輸出與 TeX Live 或 MikTeX 完全一致。TeXlyre 等新興平台已在 2026 年整合 SwiftLaTeX 並加入 TeX Live 2026 的 WASM 版本，提供含 LuaTeX 的三引擎選擇。
技術架構
專案主體以 C（58%）與 C++（40.5%）撰寫，透過 Emscripten 工具鏈交叉編譯為 .wasm 二進位。開發者在網頁中引入 JavaScript API，即可將 .tex 檔案上傳至 WASM 記憶體檔案系統、觸發編譯，並取回 PDF 位元組流與編譯日誌。執行速度約為原生二進位的 1/2。
- XeTeX 引擎（
xetex.wasm）：支援 UTF-8 與 OpenType 字型，適合中日韓及多語言文件；缺少完整 ICU locale 資料，部分語言斷行行為與原生略有差異 - PdfTeX 引擎（
pdftex.wasm）：體積較小、速度較快，適合純英文文件
社群討論焦點
HN 留言中，最大挑戰被認為是字型與宏套件的載入：完整 TeX Live 發行版超過數 GB，實際部署時需要選擇性打包所需套件。WASM 的單執行緒限制也影響大型文件的編譯響應時間。TeXlyre 採用 Service Worker 快取策略緩解首次載入延遲。另一個討論熱點是離線支援——純本機執行意味著無網路環境（如飛機上）也能完整使用 LaTeX，被認為是與 Overleaf 最顯著的差異化優勢。
原始來源：SwiftLaTeX GitHub
用耦合振盪器生成圖片：Un-0 以物理動力學取代擴散模型
Unconventional AI · 2026-06-25
Unconventional AI 於 2026 年 6 月 25 日發布 Un-0，這是第一個以模擬耦合振盪器為核心計算單元的大規模圖像生成模型。它不依賴擴散排程或迭代去噪，而是讓數千個振盪器在學習到的耦合動力學下演化，以輕量解碼器將振盪相位轉換為像素。在 ImageNet 64×64 上達到 ADM FID 6.74，與早期傳統生成模型相當；程式碼與預訓練權重已開放於 GitHub（unconv-ai/Un-0）。
核心架構：Kuramoto 振盪器
Un-0 採用 Kuramoto 模型：每個振盪器以固有頻率旋轉，同時受其他振盪器的耦合力影響。推論流程分五步：隨機初始化相位、注入類別條件（class conditioning）、讓系統依學習到的耦合參數演化至時間 T、記錄各振盪器最終相位，最後以小型解碼器輸出圖像。整個架構稱為 Conditional Implicit Kuramoto Generator，解碼器僅佔總參數量約 12%。
實際效果與限制
CIFAR-10（32×32）上，最大模型（4,096 個振盪器，19.4M 參數）達到 clean-FID 8.76；ImageNet-64 上，最大模型（16,384 個振盪器，322M 參數）達到 ADM FID 6.74。消融實驗確認學習到的動力學優於隨機特徵提取，增加積分步數也能穩定改善品質，說明非線性動力學確實提供了有效計算貢獻。
目前 Un-0 仍是軟體模擬，實體振盪器晶片尚不存在。創辦人 Naveen Rao 宣稱物理硬體理論上可將能耗降低 1000 倍，但此數字是基於振盪器電路相比 GPU CMOS 的理論估算，距實際驗證仍有距離。模型需要 Python ≥ 3.11、PyTorch ≥ 2.11 及 CUDA GPU（已驗證：NVIDIA B200、H200、A100）。