Известно, что он является NP-полным, чтобы проверить, существует ли гамильтонов цикл в 3-регулярном графе, даже если он плоский (Гэри, Джонсон и Тарьян, SIAM J. Comput. 1976) или двудольный (Akiyama, Nishizeki, и Saito, J. Inform. Proc. 1980), или чтобы проверить, существует ли гамильтонов цикл в...
Ясно, что любая проблема, которая разрешима в детерминированном пространстве журналов ( ), выполняется в самое большее полиномиальное время ( ). Существует множество классов сложности между и . Примеры включают , , , , , . Широко распространено мнение , что .P L P N L L o g C F L N C i S A C i A C...
Я знаю, что это очень специфический вопрос, и я сомневаюсь, что на него ответит любой, кто еще не знаком с правилами Магии. Перекрестная публикация на Draw3Cards . Вот исчерпывающие правила игры Magic: The Gathering . Смотрите этот вопрос для получения списка всех магических карт. У меня вопрос -...
Существует богатая литература и, по крайней мере, одна очень хорошая книга, в которой излагаются известные значения твердости аппроксимации для NP-трудных задач в контексте мультипликативной ошибки (например, 2-аппроксимация для покрытия вершин оптимальна при условии UGC). Это также включает хорошо...
Граф H является ядром, если любой гомоморфизм из H в себя является биекцией. Подграф H группы G является ядром группы G, если H является ядром и существует гомоморфизм от G к H. http://en.wikipedia.org/wiki/Core_%28graph_theory%29 Учитывая граф G, какой самый известный точный алгоритм, чтобы найти...
Подсчет количества совершенных совпадений в двудольном графе сразу сводится к вычислению перманента. Поскольку поиск идеального соответствия в двудольном графе есть в NP, существует некоторое сокращение от двудольных графов к перманенту, но это может привести к неприятному полиномиальному взрыву,...
Учитывая огромную базу данных разрешенных слов (отсортированных по алфавиту) и слово, найдите слово из базы данных, которая является ближайшей к данному слову с точки зрения расстояния Левенштейна. Наивный подход, конечно, состоит в том, чтобы просто вычислить левенштейновское расстояние между...
Гипотеза реконструкции говорит о том, что графы (по крайней мере, с тремя вершинами) определяются однозначно их вершинами удаленных подграфов. Этой гипотезе пять десятилетий. В поисках соответствующей литературы я обнаружил, что следующие классы графов, как известно, восстанавливаемы: деревья...
Проблема стабильного брака: http://en.wikipedia.org/wiki/Stable_marriage_problem Мне известно, что для случая SMP возможны многие другие стабильные браки, кроме одного, возвращенного алгоритмом Гейла-Шепли. Однако, если нам дается только , число мужчин / женщин, мы задаем следующий вопрос: можем ли...
Типы и языки программирования довольно сильно фокусируются на подтипах, но, насколько я могу судить, подтипы не кажутся особенно фундаментальными. Дает ли подтип что-то большее, чем зависимые типы? Работа с зависимыми типами должна быть более трудоемкой, поэтому я могу понять, почему подтипы могут...
Я хочу сделать первый SAT решатель. Я знаю соревнования SAT и конференцию SAT, и на эту тему очень много работ. Я стартер, перегруженный стартер. С чего мне начать? В конце концов я хочу продвинуть современное состояние. Мне нужен совет специалиста о том, как начать, чтобы я не тратил свое время на...
Даны Nnn подмножеств S1, … , SNS1,…,SnS_1,\ldots,S_n из { 1 , … , д}{1,…,d}\{1,\ldots,d\} . Проверьте, есть ли множества Sя, SJSi,SjS_i,S_j с Sя⊊ SJSi⊊SjS_i \subsetneq S_j . (Если так, найдите пример, если нет, просто скажите «нет») Тривиальное решение этой проблемы проходит через все пары наборов...
Для любого языка над определите На словах состоит из всех , для которых есть одинаковой длины таким образом, что .Σ * L +1 / +2 = { х ∈ Σ * : х у ∈ L , у ∈ Σ | х | } . L 1 / 2 х у й у ∈ LLLLΣ*Σ∗\Sigma^*L1 / 2= { x ∈ Σ*: х у∈ L , y∈ Σ| х |} .L1/2={x∈Σ∗:xy∈L,y∈Σ|x|}.L_{1/2} = \{x \in \Sigma^* : xy\in...
В «Требованиях к квантовым вычислениям» Бартлетт и Сандерс суммируют некоторые из известных результатов для квантовых вычислений с непрерывной переменной в следующей таблице: Мой вопрос состоит из трех частей: Девять лет спустя, можно ли заполнить последнюю ячейку? Если столбец добавлен с...
Хорошо известно, что существует порог шума для квантовых вычислений, такой, что ниже этого порога вычисление может быть закодировано таким образом, что оно дает правильный результат с ограниченной вероятностью (с не более чем полиномиальными вычислительными издержками). Этот порог зависит от...
Это связано с вопросом: известен ли размер свидетельства для каждого языка NP, уже известного? Некоторые естественные задачи (-complete) имеют свидетелей линейной длины: удовлетворительное назначение для S A T , последовательность вершин для H A M P A T H и т. Д.Н ПNP\mathsf{NP}SА ТSATSATЧАСА МпА...
Редактировать: я сначала неправильно сформулировал свое ограничение (2), теперь оно исправлено. Я также добавил больше информации и примеров. С некоторыми коллегами, изучающими какой-то другой алгоритмический вопрос, мы смогли свести нашу проблему к следующей интересной проблеме, но мы не смогли...
РЕДАКТИРОВАТЬ (v2): в конце добавлен раздел о том, что я знаю о проблеме. РЕДАКТИРОВАТЬ (v3): Добавлено обсуждение пороговой степени в конце. Вопрос Этот вопрос в основном справочный запрос. Я не знаю много о проблеме. Я хочу знать, была ли предыдущая работа по этой проблеме, и если да, может ли...
Какие последствия может иметь доказательство гипотезы abc для tcs?
Я ищу книгу о продвинутых структурах данных, которая выходит за рамки того, что описано в стандартных учебниках, таких как Cormen, Leiserson, Rivest и Stein "Введение в алгоритмы". Книга, которую можно использовать для преподавания курса для выпускников по продвинутым структурам данных, таким как...