Q

這個符號在圖論中是什麼意思≤P？

2016-04-15 62 views 1 likes

1

在這種情況下，p應該是下標。它是否意味着小於或等於多項式時間？這個符號在圖論中是什麼意思≤P？

2016-04-15 El Fufu

+0

更多背景請。 –

+0

我試圖證明定向哈密爾頓循環≤P無向哈密爾頓循環 –

+0

這很可能是在您的教科書中定義的。從看到此符號的位置開始按相反的順序瀏覽頁面，直至找到定義。 – user2357112

A

回答

1

A≤_p乙意味着有從A到B一個polynomial-time many-one reduction，即，存在一個多項式時間計算函數f，使得對於每串x，我們有×10 9，當且僅當f （x）在B中。

2016-04-15 04:15:42

相關問題