Teoretyczne informatyka primes

2

Czy problemy PRIMES, FACTORING są znane jako P-hard?

Niech PRIMES (inaczej testowanie pierwotności ) będzie problemem: Biorąc pod uwagę liczbę naturalną , czy n jest liczbą pierwszą?nnnnnn Niech FACTORING będzie problemem: Biorąc pod uwagę liczby naturalne , m przy 1 ≤ m ≤ n , czy n ma współczynnik d przy 1 < d < m ?nnnmmm1≤m≤n1≤m≤n1 \leq …

39 cc.complexity-theory lower-bounds factoring primes p-hardness

2

Znalezienie liczby pierwszej większej niż podana granica

Jest deterministycznym algorytmem czasu wielomianowego znanym z następującego problemu: Dane wejściowe: liczba naturalna (w kodowaniu binarnym)nnn Wyjście: liczba pierwsza .p > np>np > n (Według listy otwartych problemów Leonarda Adlemana problem był otwarty w 1995 r.)

25 cc.complexity-theory open-problem nt.number-theory polynomial-time primes

1

Czy funkcja liczenia pierwszych # P jest kompletna?

Recall liczba liczb pierwszych jest funkcją zliczania liczb pierwszych . Przez „PRIMES in P”, computing jest w #P. Czy problem # P jest kompletny? A może istnieje złożony powód, by sądzić, że ten problem nie jest # P-całkowity? π( n )π(n)\pi(n)≤ n≤n\le nπ( n )π(n)\pi(n) PS Zdaję sobie sprawę, że …

20 cc.complexity-theory counting-complexity nt.number-theory comp-number-theory primes

2

Jakie są przypuszczenia TCS, które zostały udowodnione dla liczb pierwszych i małych wartości, ale okazały się fałszywe?

Czy są jakieś przypuszczenia w informatyce teoretycznej, które dotyczą jakiegoś parametru n i zostały udowodnione dla małych wartości n AND dla liczb pierwszych, ale później okazały się fałszywe? W teorii liczb takie problemy istnieją, np. jak wskazuje Aaron Meyerowitz na temat współczynników wielomianów cyklotomicznych. Z TCS znam tylko takie przykłady, …

17 big-list primes

1

Czy PRIMEGAME Conwaya generuje wszystkie podstawowe moce 2?

Większość stron, które odwiedziłem czytając ten interesujący temat, podaje coś podobnego „jedynymi potęgami dwóch (innych niż 2), które występują w tej sekwencji, są te z głównym wykładnikiem potęgi” (MathWorld) lub „Po 2 sekwencja ta zawiera następujące potęgi 2: [...], które są podstawowymi potęgami 2”. (Wikipedia) Te staranne sformułowania sugerowałyby, że …

17 reference-request primes

5

Dlaczego uczenie maszynowe może nie rozpoznawać liczb pierwszych?

Powiedzmy, że mamy reprezentację wektorową dowolnej liczby całkowitej o wartości n, V_n Ten wektor stanowi dane wejściowe do algorytmu uczenia maszynowego. Pierwsze pytanie: dla jakiego rodzaju reprezentacji można nauczyć się pierwotności / złożoności n za pomocą sieci neuronowej lub innego mapowania ML wektor-bit. Jest to czysto teoretyczne - rozmiar sieci …

13 co.combinatorics machine-learning primes

2

Jaki jest najbardziej wydajny algorytm podzielności?

b a b azaaabbbzaaabbbzaaabbbO ( m logm loglogm )O(mlog⁡mlog⁡log⁡m)O(m\log m\log\log m)mmmΩ ( m log m log log m )max { a , b }max{a,b}\max\{a,b\}Ω ( m logm loglogm )Ω(mlog⁡mlog⁡log⁡m)\Omega(m\log m\log\log m) dolna granica tego problemu? Dziękuję i pozdrawiam, i przepraszam, jeśli to takie naiwne pytanie.

12 time-complexity lower-bounds nt.number-theory primes

2

Dlaczego większość kryptografii zależy od dużych par liczb pierwszych, a nie innych problemów?

Większość obecnych metod kryptograficznych zależy od trudności faktorowania liczb, które są iloczynem dwóch dużych liczb pierwszych. Jak rozumiem, jest to trudne tylko tak długo, jak długo metoda zastosowana do wygenerowania dużych liczb pierwszych nie może być użyta jako skrót do faktoryzacji wynikowej liczby złożonej (a samo faktoring dużych liczb jest …

9 cr.crypto-security primes

Pytania otagowane jako primes