是否有一個多項式時間算法來測試某個數字的數字指數？

只要研究着名論文PRIMES is in P就會感到困惑。由於整個算法在多項式時間內運行，因此該步驟還必須在O（（log n）^ c）中完成（給定的輸入大小爲O（log n）），但是I想不出任何算法一些谷歌上搜索後擊中目標是否有一個多項式時間算法來測試某個數字的數字指數？

問題：？

是否有任何可用的算法，以測試是否在多項式時間內的一些其他數量的數量指數

感謝和最好的問候！

來源

2012-04-18 Summer_More_More_Tea

這可能更適合http://cstheory.stackexchange.com – 2012-04-18 17:54:58

是'a'知道嗎？如果是這樣，只需用'a'重複'n'，看看你最終得到1;如果我們有恆定時間分割，這需要'log_a（n）'步驟。或者，直接計算'log_a（n）'（大概是用'log（n）/ log（a）'），看看它是否是一個整數。 :) – Dougal 2012-04-18 17:56:40

@Dougal謝謝你的迴應。我認爲'a'是未知的，或者我錯過了一些東西。 IIRC，該算法的主要思想是建立一些規則來聲明組合的數量。如果索賠在這些規則下失敗，那麼該數字必須是總理的指數。這第一步消除了指數大於1的情況。 – 2012-04-18 18:01:10

如果n=a^b（對於> 1），那麼B ≤日誌 N，我們可以檢查所有b的比log n小，以測試這一點，我們可以遍歷查找從2 b登錄n，並且用於找到a我們應該在1..sqrt（n）之間進行二分搜索。但是二分法搜索需要O（logn）時間來進行迭代，最後在每一步搜索中（對於任何找到的a進行檢查），我們應該檢查是否需要O（log n），因此總搜索時間將是O（日誌 n）。可能有一種更快的方法，但知道AKS是O（這個O（日誌n）不會損害任何東西。

來源

2012-04-18 18:27:42

謝謝。這就說得通了。：） – 2012-04-19 01:12:17

如果存在b和e，其中b^e = n，則n是一個完美的冪。例如216 = 6^3 = 2^3 * 3^3是一個完美的力量，但是72 = 2^3 * 3^2不是。確定一個數是否是一個完美的能力的訣竅是知道如果該數是一個完美的冪，則指數e必須小於log2n，因爲如果e更大，那麼2^e將大於n。此外，只需要測試素數e，因爲如果一個數對於複合指數來說是一個完美的力量，它對於複合分量的主要因素也是一個完美的力量;例如，2^15 = 32768 = 32^3 = 8^5是一個完美的立方體根，也是完美的第五根。因此，該算法是製作一個小於log2 n的素數列表並測試每一個。由於log2 n很小，素數列表甚至更小，即使對於大n，這也不是什麼大事。

你可以看到一個實現here。

來源

2012-04-18 18:23:11 user448810

它不僅僅是一個「小」的問題，而是你是否可以在O（log（n））中做所有事情的問題。 – 2012-04-18 18:52:01

外部循環在小於log2 n的素數上。由於x/log x primes小於x，所以內部循環將執行log n/log log n次。現在，log log n非常小，對於所有實際目的而言都是常量，所以我們會說外部循環是log n。每次執行內循環時，它都使用牛頓方法來計算一個根，這個根以二次方式收斂。 – user448810 2012-04-18 19:21:32

你的完整評論似乎缺少，但聽起來像O（log（n）^ 2）（我認爲只是更新答案比評論更好）。 – 2012-04-18 19:24:00

public boolean isPerfectPower(int a) { 
    if(a == 1) return true; 
    for(int i = 2; i <= (int)Math.sqrt(a); i++){ 
     double pow = Math.log10(a)/Math.log10(i); 
     if(pow == Math.floor(pow) && pow > 1) return true; 
    } 
    return false; 
}

來源

2016-04-21 18:48:33

是否有一個多項式時間算法來測試某個數字的數字指數？

回答

相關問題