Недавно я прошел через мучительный забавный опыт неформального объяснения концепции вычислительной сложности молодому талантливому программисту-самоучке, который никогда раньше не проходил формальный курс по алгоритмам или сложности. Неудивительно, что многие понятия поначалу казались странными, но...
Есть ли вероятная гипотеза сложности / криптозащиты, которая исключает возможность того, что схемы полиномиального размера имеют субэкспоненциальный размер (т. Е. с ) ограниченной глубиной ( )...
В общем, лента запросов для оракула учитывает сложность пространства ТМ. Тем не менее, кажется правдоподобным разрешить запись оракула только для записи (например, которая используется в сокращениях L-пространства). Полезна ли такая конструкция? Дает ли он какие-то особенно абсурдные...
Самостоятельная ссылка на проблему P / NP иногда подчеркивалась как барьер для ее разрешения, см., Например, статью Скотта Ааронсона, является ли P против NP формально независимой ? Одним из многих возможных решений P / NP будет демонстрация того, что проблема формально не зависит от ZFC или...
[Примечание: я полагаю, что этот вопрос никоим образом не зависит от правильности или неправильности статьи Деолаликара.] В блоге Скотта Ааронсона « Оптимизированный Штетл» в дискуссии о недавней попытке Деолаликара на P против NP Леонид Гурвиц сделал следующий комментарий : Я попытался понять /...
Допустим, что язык является P- плотно-близким, если существует алгоритм с полиномиальным временем, который правильно определяет почти на всех входах.LLLLLLL Другими словами, существует P , такое, что обращается в нуль, что означает Это также означает, что на равномерном случайном входе алгоритм...
Листовые языки - прекрасный способ единообразно определить множество классов сложности. Большинство классов сложности обычно определяются моделью вычисления (например, детерминированной / рандомизированной ТМ) и привязкой к ресурсу (время журнала, поли-пространство и т. Д.). Однако в формулировке...
Читая некоторые недавние темы о квантовых вычислениях ( здесь , здесь и здесь ), я вспоминаю интересный вопрос о мощности некоторой машины, сохраняющей ℓpℓp\ell_p норму. Для людей, работающих в области теории сложности, которые идут на квантовую сложность, хорошим вступительным текстом является...
Два связанных вопроса об ограниченных вычислениях глубины: 1) Предположим, что вы начинаете с n битов, и начинаться с бита i может быть 0 или 1 с некоторой вероятностью p (i) независимо. (Если это упрощает задачу, мы можем предположить, что все p (i) s равны 0,1 или 1/2.или даже то, что все они...
В статье «Сборник задач, завершенных для P» Гринлоу, Гувера и Руццо (PS) (PDF) , есть список проблем в P, которые, как известно, не находятся в NC и также не известны как P-полные. , (Этот список включает все открытые проблемы в превосходном обзоре Карпа и Рамачандрана .) Список открытых проблем...
Заданы пять связанных вопросов, и ожидается единый интегрированный ответ: В1: Существуют ли языки , которые распознаются только теми машинами Тьюринга в , показатели времени выполнения которых неразрешимы ?LLLпPP Вопрос 2: Можно ли конечно построить примеры этих машин Тьюринга? Вопрос 3: Можно ли...
В параметризованной сложности, . Предполагается, что каждое из условий является правильным.⊆ W [ 2 ] ⊆ … ⊆ W [ P ]FPT⊆W[1]FPT⊆W[1]\mathsf{FPT} \subseteq \mathsf{W}[1] ⊆W[2]⊆W[2]\subseteq \mathsf{W}[2] ⊆…⊆W[P]⊆…⊆W[P]\subseteq \ldots \subseteq \mathsf{W}[P] Если то .P = W [ P...
Предположим, у нас есть проблема, параметризованная вещественным параметром p, который «легко» решить, когда и «трудно», когда для некоторых значений , . p = p 1 p 0 p 1p=p0p=p0p=p_0p=p1p=p1p=p_1п0p0p_0п1p1p_1 Одним из примеров является подсчет спиновых конфигураций на графиках. Считая взвешенные...
Я ищу хороший обзор алгоритмов и сложности линейной алгебры (операции типа ранга, обратные, собственные значения, ... для логических, и целых / рациональных матриц) с акцентом на параллельные ( иерархия N C ) и полимерные алгоритмы , Я не мог найти недавний.FpFp\mathbb{F}_pNCNCNC Знаете ли вы...
В классе сложности есть некоторые проблемы, предположительно не входящие в класс N C , то есть проблемы с детерминированными параллельными алгоритмами. Проблема максимального потока является одним из примеров. И есть проблемы, СЧИТАЕМЫЕ быть в N C , но доказательство еще не...
Насколько быстрым должен быть недетерминированный алгоритм для полной задачи EXPTIME, чтобы подразумевать P ≠ N PP≠NPP \neq NP ? Недетерминирован алгоритм полиномиальное время будет немедленно следует это потому , что Р ≠ Е Х Р Т Я М ЕP≠EXPTIMEP \neq EXPTIME , но никто не считает , N P = Е Х Р Т Я...
Название более или менее говорит само за себя, но я думаю, я мог бы добавить немного фона и некоторые конкретные примеры, которые меня интересуют. Теоретики описательной сложности, такие как Иммерман и Фагин, охарактеризовали многие из наиболее известных классов сложности с использованием логики....
Теорема PCP гласит, что для MAX 3SAT не существует алгоритма полиномиального времени, чтобы найти назначение, удовлетворяющее условиям 7/8 выполнимой формулы 3SAT, если только .P = N Р7 / 8 + ε7/8+ε7/8+ \epsilonпзнак равно Nппзнак равноNпP = NP Существует тривиальный алгоритм полиномиального...
Обсуждение : В последнее время я проводил некоторое личное время, изучая различные вещи в сложности общения. Например, я повторно ознакомился с соответствующей главой в Арора / Барак, начал читать некоторые статьи и заказал книгу Кушилевица / Нисана. Интуитивно я хочу сравнить сложность...
Следующая интересная проблема возникла в моем исследовании недавно: МИГ: График .G ( V, E)G(V,E)G(V, E) РЕШЕНИЕ: завершение неординарного нечетного цикла, определяемое как надмножество множества ребер, так что завершенный граф обладает свойством того, что каждое ребро в содержится в нечетком...