Pytania z teorii liczb
Wiemy, że funkcja wykładnicza nad liczbami naturalnymi nie jest obliczalna w czasie wielomianowym, ponieważ wielkość wyjścia nie jest wielomianowo ograniczona wielkością danych wejściowych.exp( x , y) = xyexp(x,y)=xy\exp(x,y) = x^y Czy jest to główny powód trudności w obliczeniu funkcji...
Ostatnio Gil Kalai i Dick Lipton napisali fajny artykuł na temat ciekawej hipotezy zaproponowanej przez Petera Sarnaka, eksperta w dziedzinie teorii liczb i hipotezy Riemanna. Przypuszczenie. Niech będzie funkcją Möbiusa . Załóżmy, że f : N → { - 1 , 1 } jest funkcją A C 0 z wejściem k w postaci...
Rozważ następujący problem zliczania (lub związany z tym problem decyzyjny): Biorąc pod uwagę dwie dodatnie liczby całkowite zakodowane w systemie binarnym, oblicz ich największy wspólny dzielnik (gcd). Jaka jest najmniejsza klasa złożoności, w której występuje ten problem? Czy możesz podać...
Dowolną liczbę naturalną można traktować jako sekwencję bitową, więc wprowadzenie liczby naturalnej jest takie samo, jak wprowadzenie sekwencji 0-1, więc oczywiście występują problemy NP-zupełne z wejściami naturalnymi. Ale czy są jakieś naturalne problemy, tzn. Takie, które nie używają kodowania i...
Biorąc pod uwagę liczbę całkowitą długości n bitów, jak trudne jest wyprowadzenie liczby czynników pierwszych (lub alternatywnie liczby czynników) N ?N.NNnnnN.NN Gdybyśmy znali podstawową faktoryzację , byłoby to łatwe. Gdybyśmy jednak znali liczbę czynników pierwszych lub liczbę czynników...
Co wiadomo na temat złożoności obliczeniowej liczb całkowitych faktoringu w ogólnych polach liczbowych? Dokładniej: Nad liczbami całkowitymi reprezentujemy liczby całkowite poprzez ich binarne rozszerzenia. Jakie są analogiczne reprezentacje liczb całkowitych w ogólnych polach liczbowych? Czy...
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.)...
Jakie konsekwencje miałby dowód hipotezy abc dla
Pierwszym krokiem algorytmu testowania pierwotności AKS jest sprawdzenie, czy liczba wejściowa jest mocą doskonałą. Wydaje się, że jest to dobrze znany fakt w teorii liczb, ponieważ artykuł nie wyjaśnił go szczegółowo. Czy ktoś może mi powiedzieć, jak to zrobić w czasie wielomianowym?...
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...
Wikipedia podaje przykłady problemów, w których liczenie wersji jest trudne, natomiast wersja decyzyjna jest łatwa. Niektóre z nich liczą doskonałe dopasowania, licząc liczbę rozwiązań SAT i liczbę sortowań topologicznych.222 Czy są jeszcze jakieś inne ważne klasy (powiedzmy przykłady z sieci,...
W swoim artykule z 1995 r. „ Algorytmy czasowe wielomianowe dla faktoryzacji pierwotnej i logarytmów dyskretnych na komputerze kwantowym” Peter W. Shor omawia ulepszenie części algorytmu faktoryzacji polegającej na ustalaniu kolejności. Standardowe wyjścia algorytm , dzielnik w kolejności R o x...
Interesuje mnie złożoność rozwiązywania równań liniowych modulo k , dla dowolnego k (i ze szczególnym zainteresowaniem mocami pierwotnymi), w szczególności: Problem. Czy dla danego układu równań liniowych w nieznanych modulo istnieją jakieś rozwiązania?n kmmmnnnkkk W streszczeniu swojego...
Czy ktoś może mi pomóc z następującym problemem? Chcę znaleźć niektóre wartości ai,bjai,bja_i,b_j (mod N.NN ) gdzie i = 1 , 2 , … , K , j = 1 , 2 , … , Ki=1,2,…,K,j=1,2,…,Ki=1,2,…,K, j=1,2,…,K (na przykład K = 6K=6K=6 ), biorąc pod uwagę listę wartości K 2K2K^2 , które odpowiadają różnicom a i - b...
Zastanawiałem się, czy istnieje dobra bibliografia prób zbadania hipotezy Collatza jako formalnej gramatyki? (lub wszelkie inne próby w społeczności CS radzenia sobie z tą klasą zjawisk generatywnych i ich
Interesuje mnie „najbliższy” (i „najbardziej złożony”) problem hipotezy Collatza , który został pomyślnie rozwiązany (o czym słynie Erdos „matematyka nie jest jeszcze dojrzała na takie problemy”). Udowodniono, że klasa problemów typu „Collatz” jest nierozstrzygalna. Jednak problemy, które są nieco...
Jaka jest złożoność decyzji, czy przedział liczb naturalnych zawiera liczbę pierwszą? Wariant Sita Eratostenesa daje algorytm , w którym jest długością przedziału, a ukrywa czynniki polilarytmiczne w punkcie początkowym przedziału; czy możemy zrobić lepiej (pod względem samego...
Z uwagi na jedno z moich pytań dotyczących MathOverflow mam wrażenie, że kwestia dotycząca GCD będąc w vs. P jest zbliżona do kwestii dotyczącej Integer faktoryzacji Będąc w P vs. N P .NCNC\mathsf{NC}PP\mathsf{P}PP\mathsf{P}NPNP\mathsf{NP} Czy istnieje coś takiego jak „quantum algorytm” dla GCD...
Rozważ następujący problem testowania członkostwa w podgrupie abelian . Wejścia: Skończona grupa abelowa G=Zd1×Zd1…×ZdmG=Zd1×Zd1…×ZdmG=\mathbb{Z}_{d_1}\times\mathbb{Z}_{d_1}\ldots\times\mathbb{Z}_{d_m} o dowolnie dużych didid_i . Wytwarzające osadzone {h1,…,hn}{h1,…,hn}\lbrace...
'Biorąc pod uwagę , czy jest , ' jest -kompletny. x , y ∈ N a x 2 + b y = c N Pa,b,c∈Na,b,c∈Na,b,c\in\Bbb Nx,y∈Nx,y∈Nx,y\in\Bbb Nax2+by=cax2+by=cax^2+by=cNPNP\mathsf{NP} Do której klasy złożoności należy „Biorąc pod uwagę , czy istnieje , '? x , y ∈ N a x 2 + b y 2 = ca,b,c∈Na,b,c∈Na,b,c\in\Bbb...