Вопросы с тегом «reductions»

11
Почему NP-полные задачи не имеют сходных отношений аппроксимации?

Поскольку 2 NP-полные задачи по определению сводимы друг к другу, поэтому решение одной из них можно получить с помощью черного ящика, решающего другую, почему они не имеют сходных отношений аппроксимации (ссылаясь на их аналоги по оптимизации )? Я предполагаю, что некоторый постоянный или даже...

11
Экземпляр FPT-сокращений, который не является уменьшением за полиномиальное время

В параметризованной сложности люди используют сокращение с фиксированным параметром (FPT), чтобы доказать W [t] -твердость. Теоретически FPT-редукция не является редукцией за полиномиальное время, поскольку она может экспоненциально выполняться по параметру k. Но на практике все сокращения FPT,...

10
Улучшение общего сокращения Кука для Clique to SAT?

Я заинтересован в уменьшении клика до SAT, не делая экземпляр намного больше.kkk Клика находится в NP, поэтому ее можно уменьшить до SAT, используя логарифмическое пространство. Простое сокращение учебника Garey / Johnson увеличивает размер экземпляра до кубического размера. Тем не менее, Клик...

10
Сведение трудных задач к физическим моделям

Я ищу примеры сложных проблем (в NP или более сложных) из информатики, которые могут быть сведены к моделям физических процессов. Например, max-2-sat может быть сведен к минимизации энергии в модели Изинга. Я хотел бы найти больше примеров такого типа...

10
На разреженных комплектах и ​​P против L

Теорема Махейни говорит нам , что если есть разреженная -полное множество под полиномиальное время многие-одно сокращение, то P = N P . (См. « Разреженные комплекты для NP: Решение гипотезы Бермана и Хартманиса »)NпNPNPP=NPP=NPP = NP Известны ли последствия существования разреженных полных наборов...

9
Доказательство сложности Колмогорова неисчислимо, используя сокращения

Я ищу доказательство того, что колмогоровская сложность невычислима, используя редукцию из другой невычислимой задачи. Общим доказательством является скорее формализация парадокса Берри, чем сокращение, но должно быть доказательство путем сокращения из чего-то вроде проблемы остановки или проблемы...

9
Какие-либо формулировки SAT / SMT VRP / VRPTW (TSP, Job-Shop-Scheduling)?

Интересно, есть ли у них какие-либо подходы, формулирующие проблему маршрутизации транспортного средства с временными окнами ( VRPTW ) (как проблему решения) в качестве экземпляра SAT / SMT? (альтернатива: TSP) Например: «Есть ли правильное решение для посещения всех клиентов в пределах их...