Хорошо известно , что некоторые классы NP -проблемы Have дихотомии теорем, которые гарантируют , что каждая задача в классе является либо NP -полное или находится в P . Наиболее известным таким результатом является теорема Шефера о дихотомии , а также ряд обобщений. Насколько я понимаю, доказать...
Рассматриваемые здесь преобразователи - это те, которые Википедия называет преобразователями конечного состояния . Поведение преобразователя , то есть вычисляемого им отношения, записывается как [ T ] : слово y является выходом для x тогда и только тогда, когда x [ T ] y...
Пусть простой неориентированный граф на n вершинах и m ребрах.G = ( V, E)гзнак равно(В,Е)G=(V,E)NNnммm Я пытаюсь определить ожидаемую продолжительность работы алгоритма Вильсона для генерации случайного остовного дерева . Там показано, что O ( τ ) , где τ - среднее время удара : τ = ∑ v ∈ V π ( v )...
Следующий термин (используя bruijn-индексы): BADTERM = λ((0 λλλλ((((3 λλ(((0 3) 4) (1 λλ0))) λλ(((0 4) 3) (1 0))) λ1) λλ1)) λλλ(2 (2 (2 (2 (2 (2 (2 (2 0))))))))) Применительно к церковному номеру Nбыстро оценивается нормальная форма в нескольких существующих оценщиках, включая наивных . Тем не...
Существуют ли известные естественные примеры задач оптимизации, для которых гораздо проще найти оптимальное решение, чем оценить качество данного варианта решения? Для конкретности мы можем рассмотреть задачи оптимизации, решаемые за полиномиальное время, в форме: «заданный x, минимизируйте », где...
Гипотеза Бермана – Хартманиса: все NP-полные языки выглядят одинаково в том смысле, что они могут быть связаны друг с другом полиномиальными изоморфизмами времени [1]. Меня интересует более мелкозернистая версия «полиномиального времени», то есть, если мы используем параметризованные сокращения....
Я заинтересован в уменьшении клика до SAT, не делая экземпляр намного больше.kkk Клика находится в NP, поэтому ее можно уменьшить до SAT, используя логарифмическое пространство. Простое сокращение учебника Garey / Johnson увеличивает размер экземпляра до кубического размера. Тем не менее, Клик...
Пусть - симметрический многочлен , т. Е. Такой многочлен, что для всех и все перестановки . Для удобства можно предположить, что является конечным полем, чтобы избежать решения проблем с моделью вычислений.е: KN→ Кf:Kn→Kf:\mathbb{K}^n \to \mathbb{K}x ∈ K n σ ∈ S n Kе( х ) = е( σ( х )...
Параметризованная задача k-FLIP SAT определяется как: Вход: формула 3-CNFφφ\varphi с nnn переменные и присвоение правды σ:[n]→{0,1}σ:[n]→{0,1}\sigma : [n] \to \{0,1\} Параметр: kkk Вопрос: можем ли мы преобразовать заданиеσσ\sigma в удовлетворяющее назначение σ′σ′\sigma' за φφ\varphi перевернуть...
Существует несколько интересных классов графов с ограниченной шириной дерева. Например, деревья (treewidth 1), последовательные параллельные графы (treewidth 2), внешнепланарные графы (treewidth 2), -утерплоские графы (treewidth O (k)), графы ширины ветви k (treewidth O (k)), .. ,КkkКkk Вопрос:...
Где я могу найти введение в вероятностные автоматы и что они распознают (определенные функции из слов в )? Существует ли стандартный термин для таких функций, которые распознаются вероятностными автоматами, аналогично «обычным языкам» для того, что распознают детерминированные конечные автоматы...
Конструктивная теория типов с ее базовой интерпретацией под соответствием Карри Ховарда состоит только из полных вычислимых функций. В литературе некоторые говорили об использовании «теории вычислительных типов» для представления не-завершения в функциональных программах, но в работах, с которыми я...
Обратное включение очевидно, так же как и тот факт, что любой самоустраиваемый язык NP в BPP также находится в RP. Известно ли, что это также относится к несаморедуцируемым языкам...
Для двудольного графа с положительными весами пусть с равным максимальному совпадению весов в графе .f : 2 U → R f ( S ) G [ S ∪ V ]G=(U∪V,E)G=(U∪V,E)G = (U \cup V, E)f:2U→Rf:2U→Rf: 2^U \rightarrow \mathbb{R}f(S)f(S)f(S)G[S∪V]G[S∪V]G[S\cup V] Правда ли, что субмодулярная...
Одна из немногих вещей, которые мне не нравятся в книге Окасаки о чисто функциональных структурах данных, заключается в том, что его код полон неисчерпаемого сопоставления с образцом. В качестве примера я приведу его реализацию очередей в реальном времени (рефакторинг для устранения ненужных...
Это вдохновлено этим вопросом. Пусть будет совокупностью всех комбинаторов, которые имеют только две связанные переменные. Является ли C комбинаторно полным?СC\mathcal{C}СC\mathcal{C} Я считаю, что ответ отрицательный, однако я не смог найти ссылку для этого. Я также был бы заинтересован в ссылках...
Пусть вероятностная машина Тьюринга имеет доступ к недобросовестной монете, которая выпадает в голову с вероятностью (броски независимы). Определите как класс языков, распознаваемых такой машиной за полиномиальное время. Это стандартное упражнение, чтобы доказать, что:pppBPPpBPPpBPP_p A) Если...
Предположим, у меня есть логическая схема СCC это вычисляет некоторую функцию е: { 0 , 1}N→ { 0 , 1 }f:{0,1}n→{0,1}f:\{0,1\}^n \to \{0,1\}, Предположим, что схема состоит из логических элементов И, ИЛИ и НЕ с максимальным и минимальным разветвлениями 2. Позволять x ∈ { 0 , 1}Nx∈{0,1}nx \in...
мотивация На днях я путешествовал по городу на общественном транспорте и составил интересную графическую задачу, моделирующую проблему поиска кратчайшей связи между двумя местами. Нам всем известна классическая «задача кратчайшего пути»: ориентированный граф с длинами и двумя вершинами , найдите...
Я не смог найти в литературе точную характеристику исчезновения разрыва двойственности СДП. Или когда держится «сильная двойственность»? Например, когда кто-то переходит между Лассерром и SDP SDP, в принципе у него есть пробел в дуальности. Однако, почему-то, кажется, есть какая-то «тривиальная»...