理論計算機科學

針對相關領域的理論計算機科學家和研究人員的問答

1
維基百科怎麼說隨機圖靈機可以提供無可爭議的輸出?
提到的維基百科文章:Hypercomputation 第三段開頭為: Technically, the output of a random Turing machine is uncomputable; however, most hypercomputing literature focuses instead on the computation of deterministic, rather than random, uncomputable functions. 此外,根據另一篇...
   

-5
數學證明本身就是NP難點嗎?
在this video的8:00時,他聲稱證明事物本身就是NP問題。我正在尋找對此的更多見解。有人可以幫我解釋一下這個概念,還可以提供進一步閱讀的鏈接嗎?我試圖更好地理解複雜度類之間的關係。...
    


5
在三個維度上計算H-多核苷酸結合的複雜性
考慮一組 $ P_1,\ ldots,P_k $ 中的 $ \ mathbb {R} ^ 3 $,每個均以半空間與有理法線的交集給出(特別是它們都是凸的)。我們還獲得了目標多面體 $ Q $ ,我們可以假設它是框 $ [-1,1] ^3 $ 。 What is the complexity class of deciding whether $Q\subse...
   

10
Go的理論複雜性-最新技術
Go的理論複雜性有哪些最新進展?我知道一些有關Go的複雜性的早期作品: Go is polynomial-space hard 證明Go符合PSPACE標準。 Ladders are PSPACE-complete 證明了梯子是PSPACE完整的。 Go endgames are PSPACE-hard 證明Go殘局(或yose)對PSPACE很難。 ...
   

7
PCP定理原始證明中使用的曲線的技術引理
我正在閱讀here的證明,發現一個技術引理似乎是不正確的(它的證明簡短而又含糊不清)。我知道這是很具體的,上下文也有問題,但我自己也無法弄清楚。在第67頁中(當證明用於低次多項式本地解碼程序的合理性的聲明時)...
   

6
$ L \ neq NL $是$ L \ subset 1NL $嗎?
日誌空間圖靈機具有一個只讀輸入磁帶,一個只寫輸出磁帶,並且最多使用 $ O(\ log n)$ 空間在其讀寫工作帶中。類 $ L $ 和 $ NL $ 包含由確定性或非確定性日誌空間確定的語言圖靈機。雙向圖靈機可以將輸入磁帶上的頭移動到...
     

2
FO(TC)下限遊戲?
有人知道有任何遊戲/代數結構為 $ FO(TC)$ 公式提供了下限方法嗎?我知道EF遊戲適用於一階和二階語句,但希望能夠確定 $ FO(TC)$ 的下限查詢有限模型。在這方面的任何幫助將不勝感激!...
   

0
NP-完全圖問題/性質列表?
是否有很好的資源可以在圖形和網絡上找到各種決策問題?對於我正在做的項目,能夠查看許多不同的問題會很有用。有找到它們的好資源嗎?...
  

1
可擴展類型理論與功能可擴展性
是功能擴展性的原則 $(\ forall x。f(x)= g(x))\暗示f = g $ ,可從ETT派生?最值得注意的是,這可以在阿格達中使用公理K導出嗎?...
   

3
兩個可計算函數組成的Kolmogorov複雜度
讓我們假設將兩個可計算函數 $ f $ 和 $ g $ 編碼為二進製字符串,因此 $ f,g \ in \ {0,1 \} ^ * $ 。我很好奇的是,我們是否可以為以下問題找到合適的上限和下限: \開始{equation}K(f \ circ g)\ tag {1}\ end {equation} 其中 $ K(\ cdot)$ 表...
  

3
凸多邊形包含關係
我有以下問題,這是我正在做的某些工作中的一個子問題,我完全被卡住了。請注意,我僅對最壞情況下的時間複雜度(而不是啟發式或其他任何東西)感興趣。 Given是 $ m $ 凸多邊形的一組 $ \ mathcal {P} $ span class = math-container > $...
    

5
函子嚴格正定的語義定義
如果我們將遞歸類型的定義視為:F : Type -> Type; T = fix F; 習慣上講函子F需要為正或嚴格為正,以避免在遞歸中不終止。我熟悉嚴格的積極性的通常語法定義,但是我正在尋找相應的語義定義,尤其是可以在系統中表達的語義定...
 

-2
最小頂點覆蓋和奇數週期
假設我們有一個沒有奇數循環的圖 G 。考慮制定為線性規劃問題的 G 的最小頂點覆蓋問題,即對於每個頂點 $ v_ {i} $ ,我們具有變量 $ x_ {i} $ ,對於每個邊 $ v_ {i} v_ {j} $ 具有約束 $ x_ {i} + x_ {j} \ geq1 $ ,對於每個變量,我們都有 ...
  

1
嵌入式簡單複合體的數據結構
我正在尋找一種數據結構,以對 $ n $ 維簡單複合體進行編碼,並在 $ \中嵌入mathbb {R} ^ {n + 1} $ 。我知道combinatorial maps可以概括平面圖的旋轉系統,而generalized maps可以進一步概括組合圖以實現非定向性。在Wikipedia中,組合圖定義...
   

3
不可免疫的術語
在計算複雜度類別的外部是通過可計算性理論(AKA遞歸理論)定義的類別。在這裡,我們獲得了眾所周知的複雜性類,例如R,RE和co-RE。但是,通過可計算性理論定義的其他內容是免疫集的概念。免疫集是您甚至無法枚舉無限子...
  

1
在所有多項式運行時上歸納?
曾經有一種證明技術,可以通過歸納地表示沒有任何語言來表明某語言不在 $ \ mathrm {P} $ 中。語言為 $ \ mathrm {TIME}(n ^ k)$ ? $ k $ ?例如: $ L \ notin \ mathrm {TIME}(n ^ 0)$ , $ L \ notin \ mathrm {TIME}(n ^ k)\ rightarrow L \ notin \ mathrm ...
  

7
具有適當顏色的邊的圖同構的複雜性(參考要求)
邊緣彩色圖形 $ G $ 是一個圖形,其邊緣用顏色標記(通常由整數表示)。如果 $ G $ 中的所有相鄰邊緣具有不同的顏色,則這種著色為適當。我最近意識到,可以在多項式時間內測試兩個這樣的圖之間的同構。參數很簡單,問題...
   

2
複雜度未知的最大子圖問題
讓 $ Q $ 為多項式時間可確定的圖形屬性。在圖中,我們稱一個子圖 $ S $ 為 $ Q $ -subgraph,如果 $ S $ 具有屬性 $ Q $ 。考慮以下優化問題: 最大 $ Q $ -子圖問題 輸入:簡單的無向圖 $ G =(V,E)$ 和一個整數 $ \ ell $ ,帶有 $ 1 \ leq \...
    


Next page