Полимайм и алгоритм многопространства для определения главного пересечения n дискретных монотонных функций

Немного подставного лица: я специалист по информатике и работаю программистом. Итак, извините, если эта подсказка кажется несколько за пределами левого поля - я обычно играю с математической симуляцией и открываю задачи, когда мне нечего делать.

Играя с гипотезой Римана , я определил, что главный разрыв может быть уменьшен до рекуррентного отношения, основанного на пересечении всех дополнительных функций, образованных кратными каждого предыдущего простого числа (увлеченные наблюдатели заметят, что это обобщение Решето Эратосфена ). Если это не имеет для вас никакого смысла, не волнуйтесь - это все еще подставное лицо. $n-1$

Видя, как эти функции связаны, я понял, что следующий экземпляр каждого простого числа может быть сведен к первому пересечению этих функций, повторяющихся бесконечно. Тем не менее, я не мог определить, можно ли это отследить в polytime и polyspace. Таким образом: я ищу алгоритм, который может определить первое пересечение дискретных (и, если применимо, монотонных) функций в полиномиальном времени и пространстве. Если такого алгоритма в настоящее время не существует или он может существовать, достаточно краткого доказательства или ссылки. $n$

На данный момент наиболее близким является алгоритм проекции Дикстры (да, это RL Dykstra, а не Edsger Dijkstra ), который, я считаю, сводится к проблеме целочисленного программирования и, следовательно, NP-сложен. Точно так же, если каждый выполняет пересечение транзитивного множества всех применимых точек (поскольку они в настоящее время понимаются как ограниченные), мы все равно должны ограничиться показательным пространством для нашего повторения из-за текущей слабой границы простых чисел для любого действительного (и, следовательно, пространства для каждого простого ). $\ln(m)$ $m$ $e^n$ $n$

Во всем мире мне интересно, если мое понимание сокращения проблемы неверно. Я не собираюсь в ближайшее время разгадывать гипотезу Римана (или любую глубокую, открытую проблему в этом пространстве). Скорее я стремлюсь узнать больше об этом, играя с проблемой, и я наткнулся на загадку в своем исследовании.

algorithms reference-request discrete-mathematics MrGomez
источник

Например, под пересечением двух функций

вы имеете в виду значения

такие как

f

$f$

g

$g$

n

$n$

f (n) = g (n)

$f(n)=g(n)$

Дейв Кларк,

@DaveClarke Правильно. Простите за краткость и недооценку проблемы; Я открыто признаю, что этот вопрос может быть улучшен сейчас, когда его формулировка немного яснее.

MrGomez

@MrGomez, это произвольные монотонные функции или есть еще какое-то ограничение на них?

user834

@ user834 Повторяя мое первоначальное намерение с этим постом, это было для изучения главного пересечения ансамбля функций, связанных одной переменной (например:

). С тех пор я суммировал уравнение в терминах непрерывных тригонометрических функций вместо монотонных, чтобы посмотреть, может ли для композиции существовать поливаймовый и пространственный решатель. Пока что не повезло, но у меня не было возможности взглянуть на это в последние недели.

m i n (n > 2 ∣ 2 n + 1 \cap 3 n + 1 \cap 3 n + 2)

$min(n > 2 \mid 2n+1 \cap 3n+1 \cap 3n+2)$

МрГомез

Дикстра и Дейкстра - это одно и то же имя. «y» является лигатурой для «ij», то есть «буквы» в голландском алфавите: en.wikipedia.org/wiki/IJ_(digraph) .

Юваль Фильмус

Определение, пересекаются ли две монотонные функции, заданные как программы, не вычислимо. Точно так же определение первого пересечения под обещанием, что оно существует, «произвольно сложно» (определенно не polytime).

$P$ $f_P$ $n$ $1$ $P$ $n$ $f_P$ $1$ $P$ $P$ $f_P$ $1$

$T$ $T$

Юваль Фильмус
источник

Мне очень нравится этот ответ. Он краткий, достаточно общий, чтобы охватить сферу моего вопроса, и связывает мою проблему с аспектом, который я не рассматривал: неразрешимость проблемы остановки. Это будет хорошо. Спасибо!

Мр Гомез

Полимайм и алгоритм многопространства для определения главного пересечения n дискретных монотонных функций

Ответы: