Самая известная нижняя оценка сложности детерминированного времени для естественной задачи в NP

25

Это ответ на основные нерешенные проблемы теоретической информатики? Вопрос гласит, что он открыт, если конкретная проблема в NP требует времени .Ω(n2)

Просмотр комментариев под ответом заставил меня задуматься:

Помимо заполнения и подобных уловок, какова наиболее известная нижняя граница сложности времени на детерминированной машине ОЗУ (или многопленочной детерминированной машине Тьюринга) для интересной проблемы в NP (которая сформулирована естественным образом)?

Есть ли естественная проблема в NP, которая, как известно, неразрешима в квадратичном детерминированном времени на разумной модели машины?

По сути, я ищу пример, исключающий следующее утверждение:

любая естественная проблема NP может быть решена за времени.O(n2)

Известны ли нам какие-либо проблемы NP, схожие с теми, которые описаны в статье Карпа 1972 года или в работе Гарея и Джонсона 1979 года, для которой требуется детерминированное время? Или, насколько нам известно, все интересные природные проблемы NP могут быть решены за детерминированное время?O ( n 2 )Ω(n2)O(n2)

редактировать

Уточнение, чтобы устранить любую путаницу, возникающую из- за несоответствия между нижней границей, а не верхней границей : я ищу проблему, которую, как мы знаем, мы не можем решить в . Если задача удовлетворяет более строгому требованию, что требуется время или (для всех достаточно больших входных данных), тогда лучше, но бесконечно часто.Ω ( n 2 ) ω ( n 2 )o(n2)Ω(n2)ω(n2)

анонимное
источник
5
единственные суперлинейные нижние границы, которые я знаю для естественных проблем в NP, - это компромиссы между SAT и пространственно-временным пространством ( dl.acm.org/citation.cfm?doid=1101821.1101822 , и есть дальнейшая работа @RyanWilliams, которая будет знать гораздо больше) , и они ничего не говорят, если пространство разрешено быть линейным.
Сашо Николов
@SashoNikolov, пространственно-временные результаты для SAT, и нет никаких сокращений от многих естественных проблем NP к SAT, где размер вывода линейно ограничен размером ввода. нижняя граница для некоторой естественной проблемы необходимости НП не подразумевает более сильный результат для SAT , чем в настоящее время известно. Ω(n2)
Аноним
1
я говорю, что не знаю никакой суперлинейной нижней границы для любой другой естественной задачи NP
Сашо Николов
Как вы используете заполнение для получения искусственной проблемы в NP с нижней границей сложности времени ? Ω(n2)
Робин Котари
@RobinKothari, возьмите проблему в DTIME ( ) и добавьте ее. Доказательство опирается на теорему недетерминированной иерархии времени, и заполнение не было правильным способом ссылки на пример. Мы можем взять проблему NP в NTIME ( ) напрямую. Ω ( n 2 )Ω(2n)Ω(n2)
Аноним

Ответы:

16

Адачи, Ивата и Касаи в статье JACM 1984 года по сокращению показывают, что игра Cat и -Mice имеет нижний предел времени . Проблема в P для каждого . Задача играется на ориентированном графе. Ходы состоят из чередующихся кошек и одной из мышей. Мыши выигрывают, если они могут приземлиться на назначенном сырном узле, прежде чем кошка приземлится на них. Вопрос в том, имеет ли кот вынужденную победу. Это на самом деле полная проблема, поэтому нижняя граница действительно основана на диагонализации, которая дает временную иерархию.n Ω ( k ) k kknΩ(k)kk

Гранджин показал, что нижняя граница времени Пиппенгера, Пола, Семереди и Троттера относится к кодированию SAT, хотя результат Сантханама может его включить.

В дополнение к пространственно-временным нижним границам для SAT, упомянутым в других комментариях, существует ряд работ по нижним границам программы ветвления, которые подразумевают пространственно-временные компромиссы для машин Тьюринга. Для таких задач, как БПФ, сортировка или вычисление универсальных хеш-функций, есть квадратичный компромисс нижних границ Бородина-Кука, Абрахамсона, Мансура-Нисана-Тивари, но они предназначены для функций со многими выходами. Для решения проблем в P, существуют временные ограничения, которые применяются для временных границ, которые но они слабее, чем известные для SAT.O(nlogn)

Пол Бим
источник
есть идеи по поводу игры в кошки-мышки с NP?
vzn
12

Классический результат, о котором я знаю, связан с Полом, Пиппенгером, Семереди и Троттером (1983) и отделяет детерминистическое от недетерминированного линейного времени.

Затем, есть более недавний результат Fortnow, Lipton, van Melkebeek и Viglas (2004), который уже упоминался. Уникальность этого результата заключается в том, что это результат компромисса между пространством и временем, ограничивающий пространство и время.

ω(nlogn)

NPO(n2)

PNPO(n2)


NP

  1. DTIME(f(n))f(n)=Ω(n2logn)ω(n2)
  2. NTIME(f(n))f(n)=ω(n2)
  3. SPACE(f(n))f(n)=ω(n2/logn)

Приведенные выше нижние оценки должны быть выполнены для битовой сложности задачи.

NP

chazisop
источник
3
вопрос задается о естественной проблеме
Сашо Николов
nkΩ(n2)Ω(n2)
@ Аноним, ты говоришь, что SAT не является естественной проблемой?
Сашо Николов
@SashoNikolov, SAT - это естественная проблема. Однако результат не дает положительного ответа на мой вопрос. Поэтому я интерпретировал это как высказывание, что лучшего ответа на мой вопрос не известно. Это не должно быть так. В этом смысле это не отвечает на мой вопрос.
Аноним
2
Я попытаюсь в последний раз: хотя вы правы в том, что такого смысла нет, я совершенно уверен, что не существует известной безусловной квадратичной нижней границы для детерминированного времени для любой естественной проблемы NP. Это не следует из результатов SAT; это просто положение дел
Сашо Николов
2

Возможно, вполне естественным примером является ограниченная во времени колмогоровская сложность :

kf(n)nxM|M|<f(|x|)Mx|x|k

Марцио де Биаси
источник
Спасибо, это не совсем искусственно, но я не нахожу это удовлетворительным естественным примером.
Аноним
2
Ω(nk)
@SashoNikolov: я удалил часть Рэмси ... она нуждается в формальном доказательстве :-(
Марцио Де Биаси
-7

Это просто повторяет тот же вопрос о P = NP по-другому, если вы можете доказать, что он неразрешим в квадратичном времени, или найти абсолютную нижнюю границу, вы бы доказали P! = NP

Алекс Гонопольский
источник
11
Почему квадратичная нижняя оценка естественной задачи в NP показывает P! = NP?
Робин Котари