本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：工作論文
- 編號：工作論文 #315
- 日期：2026-03-18
摘要
我們提出一個簡單、自然的#P-完全問題。設G為有向圖，k為正整數。我們定義 q(G; k) 如下。在每個頂點 v 處，我們放置一個 k 維複向量 xv 。我們在所有邊 (u, v) 上求內積 <xu , xv > 的積。最後，q(G; k) 是該乘積的期望，其中 xv 是均勻且獨立於所有範數 1 的向量（或者，從高斯分佈）選擇的。我們證明 q(G; k) 與 G 的循環劃分多項式成正比，因此對於任何 k > 1 來說它是#P-完全的。