Вопросы по теории чисел
Мы знаем, что экспоненциальная функция над натуральными числами не вычисляется за полиномиальное время, поскольку размер выходных данных не ограничен полиномиально по размеру входных данных.ехр( х , у) = хYехр(Икс,Y)знак равноИксY\exp(x,y) = x^y Является ли это основной причиной сложности...
Недавно Гил Калай и Дик Липтон написали хорошую статью на интересную гипотезу, предложенную Питером Сарнаком, экспертом по теории чисел и гипотезе Римана. Гипотеза. Пусть - функция Мёбиуса . Предположим, что является функцией с входом в виде двоичного представления , тогда f : N → { - 1 , 1 }µ ( k...
Рассмотрим следующую проблему подсчета (или связанную с ней проблему решения): учитывая два натуральных числа, закодированных в двоичном виде, вычислим их наибольший общий делитель (gcd). В каком классе наименьшей сложности содержится эта проблема? Можете ли вы предоставить ссылку? В этом вопросе...
Любое натуральное число может рассматриваться как битовая последовательность, поэтому ввод натурального числа аналогичен вводу последовательности 0-1, поэтому проблемы с NP-заполнением с натуральными входами, очевидно, существуют. Но есть ли естественные проблемы, то есть те, которые не используют...
Учитывая целое число длиной битов, насколько сложно вывести число простых факторов (или, альтернативно, число факторов) из ?n NNNNNnnNNN Если бы мы знали первичную факторизацию , то это было бы легко. Однако, если бы мы знали количество основных факторов или число общих факторов, неясно, как мы...
Что известно о вычислительной сложности факторизации целых чисел в полях общего числа? Более конкретно: Над целыми числами мы представляем целые числа через их двоичные расширения. Что такое аналогичные представления целых чисел в полях общего числа? Известно ли, что первичность над числовыми...
Является ли детерминированный алгоритм за полиномиальное время известным для следующей задачи: Ввод: натуральное число (в двоичной кодировке)Nnn Выход: простое число .р > нp>np > n (Согласно списку открытых проблем Леонарда Адлемана, проблема была открыта в 1995 году.)...
Какие последствия может иметь доказательство гипотезы abc для tcs?
Первым шагом алгоритма тестирования простоты AKS является проверка, является ли входное число идеальной степенью. Похоже, что это хорошо известный факт в теории чисел, поскольку в статье это не объясняется подробно. Может кто-нибудь сказать мне, как сделать это за полиномиальное время?...
Напомним число простых чисел - функция подсчета простых чисел . Посредством «PRIMES in P» вычисление находится в #P. Проблема № P-завершена? Или, может быть, есть сложная причина полагать, что эта проблема не является # P-полной? π(n)π(n)\pi(n)≤n≤n\le nπ ( n )π(n)π(n)\pi(n) PS Я понимаю, что это...
В Википедии приводятся примеры проблем, где версия для подсчета трудна, а версия для принятия решения проста. Некоторые из них подсчитывают идеальные соответствия, подсчитывают количество решений для SAT и количество топологических сортировок.222 Существуют ли другие важные классы (например,...
В своей статье 1995 года « Алгоритмы полиномиального времени для первичной факторизации и дискретных логарифмов на квантовом компьютере» Питер У. Шор обсуждает усовершенствование порядка упорядочения своего алгоритма факторизации. Стандартные выходы алгоритма r′r′r' , делитель порядка rrr из xxx по...
Меня интересует сложность решения линейных уравнений по модулю k для произвольного k (и с особым интересом к простым степеням), а именно: Проблема. Для данной системы из линейных уравнений по неизвестным по модулю , существуют ли какие-либо решения?н кmmmnnnkkk В аннотации к своей статье Структура...
Кто-нибудь может мне помочь со следующей проблемой? Я хочу найти некоторые значения a i , b jai,bja_i,b_j (mod NNN ), где i = 1 , 2 , … , K , j = 1 , 2 , … , Ki=1,2,…,K,j=1,2,…,Ki=1,2,…,K, j=1,2,…,K (например, К = 6K=6K=6 ), учитывая список значений К 2K2K^2 которые соответствуют различиям a i - b...
Мне было интересно, есть ли хорошая библиография попыток исследовать гипотезу Коллатца как формальную грамматику? (или любые другие попытки в сообществе CS иметь дело с этим классом порождающих явлений и их «препятствующими»...
Меня интересует «ближайшая» (и «самая сложная») проблема к гипотезе Коллатца , которая была успешно решена (на что Эрдос сказал, что «математика еще не созрела для таких задач»). Было доказано, что класс "коллатцовых" проблем неразрешим. Тем не менее, проблемы, которые в некоторой степени похожи,...
В чем сложность определения, содержит ли интервал натуральных чисел простое число? Вариант решета Эратосфена дает алгоритм, где L является длина интервала и ~ Шкуры поли-логарифмические факторы в исходной точке интервала; мы можем сделать лучше (с точки зрения L только)?O~(L)O~(L)\tilde...
Из комментариев на один из моих вопросов о MathOverflow у меня возникает ощущение, что вопрос о GCD в vs. похож на вопрос о целочисленной факторизации в vs. .N CNС\mathsf{NC}пп\mathsf{P}пп\mathsf{P}Н ПNп\mathsf{NP} Существует ли что-то вроде алгоритма «квант » для GCD, поскольку существует алгоритм...
Рассмотрим следующую задачу проверки принадлежности к абелевой подгруппе . Входы: Конечная абелева группа с произвольно большим .G = Zd1× Zd1… × ZdмG=Zd1×Zd1…×ZdmG=\mathbb{Z}_{d_1}\times\mathbb{Z}_{d_1}\ldots\times\mathbb{Z}_{d_m}dяdid_i Производящая-набор { ч1, ... , чN}{h1,…,hn}\lbrace...
«Если , существует ли x , y ∈ N , a x 2 + b y = c » является N P -полным.a,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} К какому классу сложности относится «При условии , существуют ли x , y ∈ N , a x 2 + b y 2 = c »?a,b,c∈Na,b,c∈Na,b,c\in\Bbb...