Этот вопрос возникает из чистого любопытства (он возник, когда я думал о том, чтобы отменить перетасовку строки , но я не уверен, действительно ли это связано), поэтому я надеюсь, что это уместно. Существуют различные графические продукты, и я заинтересован в любом из них здесь. В чем сложность...
В свете недавнего результата Arora, Barak и Steurer, Субэкспоненциальные алгоритмы для уникальных игр и смежных задач , я заинтересован в графовых задачах, которые имеют субэкспоненциальные алгоритмы времени, но полагают, что они не являются полиномиально разрешимыми. Известным примером является...
Есть ли (желательно натурального) 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...
Хорошо известной характеристикой экземпляров -SAT является отношение числа предложений m к числу переменных n , т. Е. Частное ρ = m / n . Для каждого k существует пороговое значение α st \ для ρ ≪ α , большинство случаев выполнимо, а для ρ ≫ α большинство случаев неудовлетворительно. Было проведено...
Предположим, у нас есть класс объектов (например, графы, строки) и отношение эквивалентности для этих объектов. Для графов это может быть изоморфизм графов. Для строк мы можем объявить две строки эквивалентными, если они являются анаграммами друг друга. Я заинтересован в вычислении представителя...
Это ответ на основные нерешенные проблемы теоретической информатики? Вопрос гласит, что он открыт, если конкретная проблема в NP требует времени .Ω ( n2)Ω(n2)\Omega(n^2) Просмотр комментариев под ответом заставил меня задуматься: Помимо заполнения и подобных уловок, какова наиболее известная нижняя...
Хорошо известно, что любое доказательство, решающее вопрос P против NP, должно преодолевать релятивизацию , естественные доказательства и барьеры алгебраизации . Следующая диаграмма разбивает «пространство доказательств» на различные области. Например, соответствует набору доказательств, которые...
Для заданного неориентированного и невзвешенного графа и четного целого числа , какова вычислительная сложность подсчета множеств вершин таких что и подграф графа ограниченный множеством вершин допускает идеальное совпадение? Является ли сложность # P-полной? Есть ли ссылка на эту проблему?k S ⊆ V...
Рассмотрим следующую проблему: учитывая формулу CNF и присвоение, которое удовлетворяет этой формуле, есть ли другое удовлетворяющее назначение для этой формулы? В чем сложность этой проблемы? (Это наверняка есть в NP, но это также NP-hard?) Что если вам не дано назначение, и вы просто хотите...
Для любого n>0n>0n > 0 я говорю, что последовательность целых чисел в является -полной, если для каждой перестановки из , записанная как последовательность попарно различных целых чисел , последовательность является подпоследовательностью , т. е. существуеттакой, что для всех .{ 1 , … , n } n...
Согласно D. den Hertog, «Подход с внутренней точки к линейному, квадратичному и выпуклому программированию», 1994 , линейная программа с переменными, n ограничениями и точностью L разрешима за O ( n 3 L ) времени. Это было улучшено?NNnNNnLLLO ( n3Л...
Я читал в нескольких статьях, что существование односторонних функций широко распространено. Может кто-то пролить свет на то, почему это так? Какие у нас аргументы в пользу существования односторонних...
Извиняюсь за вопрос, который обязательно должен быть во многих стандартных ссылках. Мне любопытно точно вопрос в названии, в частности, я имею в виду булевы схемы, без ограничений по глубине. Я поместил «наименьшее» в кавычки, чтобы учесть, что существует множество разных классов, которые, как...
Эй, ребята, я понимаю, что уловка заполнения позволяет нам переводить классы сложности вверх - например, . Заполнение работает, «раздувая» ввод, выполняя преобразование (скажем, от к ), что приводит к «волшебному» алгоритму, который вы можете запустить на дополненном вводе. Хотя это имеет...
Что известно о вычислительной сложности факторизации целых чисел в полях общего числа? Более конкретно: Над целыми числами мы представляем целые числа через их двоичные расширения. Что такое аналогичные представления целых чисел в полях общего числа? Известно ли, что первичность над числовыми...
Знаете ли вы интересные последствия (стандартных) гипотез в теории сложности в других областях математики (т.е. вне теоретической информатики)? Я бы предпочел ответы где: гипотеза теории сложности является как можно более общей и стандартной; Я также согласен с последствиями сложности конкретных...
Конечно, некоторые результаты сложности могут рухнуть для унарных языков, но мне интересно, есть ли где-нибудь опрос, обобщающий известные результаты в этом случае: своего рода зоопарк сложности для унарных языков. Знаете ли вы о такой...
Вопрос: Какова самая известная нижняя граница размера формулы для явной функции в AC 0 ? Существует ли явная функция с нижней границей Ω(n2)Ω(n2)\Omega(n^2) ? Задний план: Как и большинство нижних границ, трудно найти нижние границы размера формулы. Меня интересуют нижние границы размера формулы...
Каковы последствия наличия полных проблем в ?Nп∩ c o NпNP∩coNPNP\cap
Существуют ли какие-либо NP-полные задачи, для которых известен алгоритм, согласно которому ожидаемое время выполнения является полиномиальным (для некоторого разумного распределения по экземплярам)? Если нет, то существуют ли проблемы, для которых было установлено существование такого алгоритма?...