Pytania otagowane jako nt.number-theory

Pytania z teorii liczb

3
Złożoność funkcji wykładniczej
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 wykładniczej, czy też wykładnictwo wykładnicze jest z natury trudne do obliczenia, …
3
złożoność największego wspólnego dzielnika (gcd)
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ć referencje? W tym pytaniu nie interesują mnie przede wszystkim asymptotyczne …
2
Jak trudno policzyć liczbę czynników całkowitych?
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 ogólnych, nie jest jasne, w jaki sposób ustalilibyśmy faktyczne czynniki pierwsze.NNN Czy …
6
Czy istnieje naturalny problem natury naturalnej, który jest NP-zupełny?
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 specjalnej interpretacji cyfr? Na przykład „Czy na pierwsze?” jest takim …
2
Złożoność faktoringu w polach liczbowych
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 wiadomo, że pierwszeństwo nad polami liczbowymi ma postać P lub BPP? Jakie są najbardziej znane …
5
Łatwe problemy z trudnymi do zliczenia wersjami
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, drzew, teorii liczb i tak dalej)? Czy istnieje kompendium takich …
1
Czy rozwiązywanie układów równań modulo w dla złożone?
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 artykułu Struktura i znaczenie klas logspace-MOD w klasach Mod k L , Buntrock, …
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.