Pytania otagowane jako nt.number-theory

Pytania z teorii liczb

4
Reprezentacje base-k w domenie wielomianu - czy jest ona pozbawiona kontekstu?
W rozdziale 4 Drugiego kursu teorii automatu Jeffreya Shallita następujący problem wymieniono jako otwarty: p(n)p(n)p(n)∈Np(n) \in \mathbb{N}n∈Nn \in \mathbb{N} { p ( n ) ∣ n ⩾ 0 }){p(n)∣n⩾0}\{p(n) \mid n \geqslant 0\} jest pozbawione kontekstu, tylko wtedy, gdy stopieńwynosi.ppp ⩽ 1⩽1\leqslant 1 Jaki jest teraz jego status (na październik …
1
Czy istnieje algorytm kwantowy NC do obliczania GCD?
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 jak jest kwantowa wielomian czas ( B Q …
2
Jaki jest „najbliższy” problem hipotezy Collatza, który został pomyślnie rozwiązany?
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 podobne, takie jak gra MIU Hofstadtera (rozwiązane, ale co prawda bardziej …
2
Złożoność testowania członkostwa dla skończonych grup abelowych
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 h_1,\ldots,h_n\rbrace podgrupy H⊂GH⊂GH\subset G . Element b∈Gb∈Gb\in G . Wyjście: „tak”, jeżeli b∈Hb∈Hb\in H i „nie” w innym miejscu. Pytanie: Czy ten problem można skutecznie rozwiązać na klasycznym …
3
Użycie sekwencji de Bruijn do znalezienia liczby całkowitej
Sean Anderson opublikował nieco hacków zawierających algorytm Erica Cole'a, aby znaleźć liczby całkowitej bit w operacjach z mnożeniem i wyszukiwaniem.N v O ( lg ( N ) )⌈ log2)v ⌉⌈log2)⁡v⌉\lceil\log_2 v \rceilN.N.NvvvO ( lg( N) )O(lg⁡(N.))O(\lg(N)) Algorytm opiera się na „magicznej” liczbie z sekwencji De Bruijn. Czy ktoś może wyjaśnić …
1
„Przepełnienie” w rozszerzonym algorytmie euklidesowym
Przepraszam, jeśli mylę się z miejscem zadawania pytania (może powinienem przejść do stackoverflow.com/mathoverflow.net?). Ciekawe, jeśli istnieje dowód, że podczas oceny rozszerzony algorytm euklidesową współczynnikom Bézout użytkownika (to jest y i T w tożsamość jako + Bt = GCD ( , b )) nie przekracza około rozsądne wartości (w zależności od …
2
Skutecznie uzyskuje bity N! ?
Biorąc pod uwagę i , czy możliwe jest uzyskanie M -tego bitu (lub cyfry dowolnej małej podstawy) N! w czasie / przestrzeni O (P (ln (N), LN (M))) , gdzie p (x, y) jest kilka funkcji wielomianowej w X i Y ?M M N !N.N.NM.M.MM.M.MN.!N.!N!p ( x , y ) …
1
Porównywanie dwóch produktów z list liczb całkowitych?
Załóżmy, że mam dwie listy liczb całkowitych dodatnich o ograniczonej męskości i biorę iloczyn wszystkich elementów każdej listy. Jaki jest najlepszy sposób ustalenia, który produkt jest większy? Oczywiście mogę po prostu obliczyć każdy produkt, ale mam nadzieję, że istnieje bardziej wydajne podejście, ponieważ liczba cyfr w produktach wzrośnie liniowo wraz …
1
Zredukowanie podstawowych produktów faktoringowych do faktoringowych liczb całkowitych (w przeciętnym przypadku)
Moje pytanie dotyczy równoważności bezpieczeństwa różnych kandydujących funkcji jednokierunkowych, które można zbudować w oparciu o twardość faktoringu. Zakładając problem FAKTORING: [Biorąc pod uwagę dla losowych liczb pierwszych , znajdź , ]P , Q &lt; 2 n P QN.= PQN=PQN = PQP., Q &lt; 2nP,Q&lt;2nP, Q < 2^nP.PPQQQ funkcja nie może …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.