Меня интересует естественное обобщение знаменитой 15-головоломки , где вам нужно сдвигать блоки, пока вы не отсортируете все заданные числа (обычно есть разрыв в 1 блок). Теперь обобщение должно было бы увеличить размер головоломки с 15 до , где одно поле свободно. Я создал небольшую иллюстрацию...
Есть ли (желательно натурального) NP-полный язык L⊆{0,1}∗L⊆{0,1}∗L\subseteq \{0,1\}^* , такое , что для любого имеет место ? Другими словами, содержит ровно половину всех битных экземпляров.n≥1n≥1n\geq 1 |L∩{0,1}n|=2n−1|L∩{0,1}n|=2n−1|L\cap...
Доступ к оракулу обеспечит значительное, сверхполиномиальное ускорение для всего в (при условии, что набор не пуст). Тем не менее, не совсем ясно, сколько выиграет от этого доступа к оракулу. Конечно, ускорение в не может быть суперполиномиальным, но оно может быть полиномиальным. Например, можем...
Ласло Бабаи недавно доказал, что проблема изоморфизма графа находится в квазиполиномиальном времени . См. Также его выступление в Чикагском университете, заметки о выступлениях Джереми Куна GLL, пост 1 , GLL, пост 2 , GLL, пост 3 . Согласно теореме Ладнера, если , то не является пустым, т. содержит...
Допустим, что язык является P- плотно-близким, если существует алгоритм с полиномиальным временем, который правильно определяет почти на всех входах.LLLLLLL Другими словами, существует P , такое, что обращается в нуль, что означает Это также означает, что на равномерном случайном входе алгоритм...
Знаменитая гипотеза об изоморфизме Бермана и Хартманиса говорит, что все -полные языки полиномиально по времени изоморфны (p-изоморфны) друг другу. Ключевое значение гипотезы является то , что она предполагает P ≠ N P . Она была опубликована в 1977 году, и часть подтверждающих доказательств, что...
Можно ли алгоритмически проверить, является ли вычисляемое число рациональным или целым? Другими словами, возможно ли для библиотеки, которая реализует вычислимые числа, предоставлять функции isIntegerили isRational? Я предполагаю, что это невозможно, и что это как-то связано с тем, что невозможно...
Существуют ли какие-либо NP-полные проблемы с бесконечным подмножеством экземпляров такие, что принадлежность к может быть решена за полиномиальное время, и для всех , может быть решена за полиномиальное время? (Предполагая )ΦΦ\Phix ∈ Φ x P ≠ N PΦΦ\Phix ∈ Φx∈Φx \in \PhiИксxxп≠ NпP≠NPP \neq...
Обычно используемые алгоритмы хэширования паролей работают сегодня так: солить пароль и подавать его в KDF. Например, используя PBKDF2-HMAC-SHA1, процесс хеширования пароля DK = PBKDF2(HMAC, Password, Salt, ...). Поскольку HMAC представляет собой двухэтапное хеширование с дополненными клавишами, а...
Для любого произвольного NP-полного языка всегда ли найдется надмножество множителей, дополнение которого также бесконечно? На /cs//q/50123/42961 была запрошена тривиальная версия, в которой суперсет не должен иметь бесконечного дополнения. Для целей этого вопроса можно предположить, что . Как...
Какова сложность следующей проблемы? Вход : гамильтонов путьв К пHHHKnКNK_n R⊆[n]2р⊆[N]2R \subseteq [n]^2 подмножество пар вершин положительное целое число kКk Запрос : существует ли сопоставление MMM такое, что для каждого (v,u)∈R(v,U)∈р(v,u) \in R , dG(v,u)≤kdграмм(v,U)≤Кd_G(v,u) \leq k ? (где...
Недавно я читал очень хорошую статью от Valiant и Vazirani, в которой показано, что если , то не может быть эффективного алгоритма для решения SAT, даже при условии, что он либо неудовлетворителен, либо имеет уникальное решение. , Таким образом, показывая, что SAT не допускает эффективного...
Когда мы хотим доказать , что является -полных, то стандартный подход выставляться полиномиальное время вычислимой сокращение многих один из известного -полных задачи в . В этом контексте нам не нужно жестко ограничивать время выполнения сокращения. Достаточно иметь любую полиномиальную границу,...
«Если , существует ли 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...
Гипотеза Бермана – Хартманиса: все NP-полные языки выглядят одинаково в том смысле, что они могут быть связаны друг с другом полиномиальными изоморфизмами времени [1]. Меня интересует более мелкозернистая версия «полиномиального времени», то есть, если мы используем параметризованные сокращения....
С начала 70-х годов известно, что и не равны (потому что не является замкнутым в полиномиальном времени многих одно сокращение, в отличие от ). Однако, насколько мне известно, до сих пор не ясно, является ли один класс подмножеством другого, или они несопоставимы, то есть и оба непусты.NPNP{\bf...
Рассмотрим связный неориентированный граф с неотрицательными весами ребер и двумя выделенными вершинами s,ts,ts,t . Ниже приведены некоторые задачи на пути, которые имеют следующую форму: найдите путь s−ts−ts-t , чтобы некоторая функция весов ребер на пути была минимальной. В этом смысле все они...
Я наткнулся на статью, опубликованную в Science, «Memcomputing NP-полных задач за полиномиальное время с использованием полиномиальных ресурсов и коллективных состояний» , в которой содержатся довольно удивительные утверждения. Memcomputing - это новая парадигма вычислений, отличная от Тьюринга, в...