Существуют ли какие-либо естественные проблемы в , которых нет (как известно / считается, что они есть) в ?U P ∩ c o U PNп∩ c o NпNP∩coNPNP \cap coNPUп∩ c o UпUP∩coUPUP \cap coUP Очевидно, что большая часть, о которой все знают в - это вариант факторинга для решения (не имеет ли коэффициент размера...
Хорошо известно, что направленная st-связность является полной. Прорыв результат Рейнгольд показал , что неориентированный ст-связность в . Известно, что направленная st-связность находится в . Cho и Huynh определили параметризованную задачу о ранце и продемонстрировали иерархию проблем между и...
Предположим, что мы решили проблему подсчета правильных раскрасок путем подсчета взвешенных раскрасок следующим образом: каждая правильная раскраска получает вес 1, а каждая неправильная раскраска получает вес где c - некоторая постоянная, а v - число ребер с конечными точками, окрашенными...
Является ли следующая проблема NP-трудной? Учитывая конфигурацию доски для n×nn×nn\times n международных шашек , найдите один законный ход. Соответствующая задача для американских шашек (или английских шашек) тривиально разрешима за полиномиальное время. Есть три основных различия между этими двумя...
Каковы будут последствия #P = FP? Меня интересуют как практические, так и теоретические последствия. С практической точки зрения меня особенно интересуют последствия для искусственного интеллекта. Указатели на бумаги или книги более чем приветствуются. Пожалуйста, не говорите, что #P = FP...
Я не могу думать ни о какой такой модели, может быть, о какой-то форме типизированного лямбда-исчисления? какой-то элементарный клеточный автомат? Это почти опровергло бы «Принцип вычислительной эквивалентности» Вольфрама: Почти все процессы, которые не являются явно простыми, могут рассматриваться...
Машине PHPHPH предоставляется оракулу доступ к случайной булевой функции f:{0,1}n→{−1,1}f:{0,1}n→{−1,1}f:\{0,1\}^n \to \{ -1,1 \} и двум спектрам Фурье ggg и hhh . Спектры Фурье функции fff определяются как F:{0,1}n→RF:{0,1}n→RF:\{0,1\}^n \to R :...
Для формулы 3CNF пусть будет максимальное число удовлетворенных положений в любом присвоении . Известно, что Max-3SAT трудно аппроксимировать (при условии P ≠ NP), то есть не существует алгоритма множителя, вход которого является формулой 3CNF , а выход которого равен числу , так что находится в...
Знаете ли вы какие-либо современные вики, посвященные задачам оптимизации NP, с их наилучшим приближением и результатом твердости? Судя по отзывам, можно предположить, что такого ресурса нет (см. В конце этого вопроса два близких варианта). - добавлено 8 февраля. Поскольку за последние два...
Этот вопрос был перенесен из переполнения стека, потому что на него можно ответить в теоретической информатике стека обмена. Мигрировал 8 лет назад . Учитывая, что соответствие Карри-Говарда так широко распространено / расширено, есть ли разница между доказательствами и программами (или между...
Известно ли что-нибудь о классе графов с тем свойством, что все максимальные независимые множества имеют одинаковую мощность и, следовательно, являются максимальными IS? Например, возьмем набор точек на плоскости и рассмотрим график пересечений между всеми отрезками между парами точек в наборе....
Это мой первый вопрос о стеке теории, так что не будь слишком груб, если я как-то нарушаю этикет) Как известно, в математике даже известные математики, суперзвезды и гении время от времени совершают серьезные ошибки. Например, и теорема о 4 цветах, и теорема Ферма дают нам драматические случаи...
О каких недостающих темах в Википедии вы бы хотели, чтобы там была статья? Это могут быть вопиющие упущения или просто темы, которые, по вашему мнению, должны иметь статью. Одна тема на ответ, пожалуйста, чтобы можно было проголосовать за наиболее разыскиваемых. Обновление 5/2/2017 : Шучи Чавла...
Учитывая регулярный язык (NFA, DFA, грамматика или регулярное выражение), как можно посчитать количество принимаемых слов на данном языке? Интерес представляют как «ровно n букв», так и «не более n букв». У Маргареты Акерман есть две статьи по теме перечисления слов, принятых NFA, но я не смог...
Шива Кинтали только что объявил (круто!) Результат, что изоморфизм графов для ограниченных графов ширины является ⊕ L- трудным≥4≥4\geq 4⊕L⊕L\oplus L . Неофициально мой вопрос: "Насколько это сложно?" Мы знаем, что неравномерно , см. Ответы на этот вопрос . Мы также знаем, что маловероятно, что ,...
Исследование сжатого представления графов было начато Гальперином и Вигдерсоном в статье 1983 года, где они доказывают, что для многих простых задач, таких как нахождение треугольника на графе, соответствующая краткая версия в NPNP\mathsf{NP} -полна. Papadimitriou и Yanakkakis дальнейшее это...
Я не теоретик информатики, но думаю, что проблема реального мира здесь. Проблема У моей компании есть несколько подразделений по всей стране. Мы предложили сотрудникам возможность работать на другом блоке. Но есть условие: общее количество работников на единицу не может измениться. Это означает: мы...
Я уверен, что все знают об эксперименте Буффона с иглой в 18-м веке, это один из первых вероятностных алгоритмов для вычисления .ππ\pi Реализация алгоритма на компьютерах обычно требует использования или тригонометрической функции, которая, даже если они реализованы в виде усеченных рядов, в...
Похоже, Джордж Гонтье и его сотрудники закончили формализацию теоремы нечетного порядка . В своей более ранней работе над теоремой о четырех цветах Гонтье изобрел кучу новых алгоритмов (в основном, вариантов BDD и графовых алгоритмов), которые были особенно пригодны для формальной проверки....
Пусть - квадратная целочисленная матрица, а n - положительное целое число. Меня интересует сложность решения следующей проблемы:MMMnnn Является ли запись в верхнем правом углу положительной?MnMnM^n Обратите внимание, что очевидный подход повторного возведения в квадрат (или любого другого явного...