Существуют ли полные проблемы для P и NP под другими видами сокращений?

Question

Я знаю, что класс сложности $ mathsf {p} $ имеет полные проблемы Wrt $ mathsf {nc} $ и $ mathsf {l} $ сокращения.

Являются ли эти два класса единственными возможными классами сокращения, в соответствии с которыми $ mathsf {p} $ имеют полные проблемы?

Кроме того, какие классы сокращения могут быть использованы для $ mathsf {np} $ помимо полинологических сокращений?

Answer 1

Ваши вопросы содержат несколько неправильных или неясных фраз. Ни «сложности класса X не имеет сокращения y», ни «мы можем использовать y снижение для сложности класса X». Кроме того, есть по крайней мере два определения, известных под названием «Сокращения полинома», оба из которых используются для изучения NP-законности: многочленное время сокращения один-один и снижение туринг полиномиального времени. Но в этом ответе я буду игнорировать разницу между сокращением многих и сокращением Тьюринга, и я сосредоточусь только на ограничениях сокращения ресурсов, потому что в противном случае ответ станет слишком длинным и не сфокусированным.

Теперь я буду повторять то, что вы захотите спросить, и ответить на них.

Существуют ли какие-либо определения сокращения в отношении того, какие NP можно определить, кроме полиномиального времени сокращения? Существуют ли какие-либо определения сокращения в отношении того, какая p-комплекса может быть определена, кроме сокращения NC и сокращения логарифмического пространства?

Как сказали Артем и Рафаэль, вы можете определить все, что вам нравится.

Существуют ли какие-либо определения сокращений, фактически используемые для изучения NP-закончины в литературе, кроме сокращения полиномиального времени? Существуют ли какие-либо определения сокращения, фактически используемые для изучения P-комплексной в литературе, кроме сокращения NC и сокращения логарифмического пространства?

Да. Например, Papadimitriou использует сокращения логического пространства на протяжении всего своего учебника [PAP94], включая определение NP-законности. (Примечание: в [PAP94] термин «L-восстановление» означает что-то совершенно отличное от сокращения логического пространства.)^k Сокращения упоминаются в [GHMRSS00]. Это особый случай сокращения NC и более общий, чем сокращение логарифмического пространства для k≥2.

Но действительно ли они разные понятия или просто разные определения для одного и того же понятия?

В настоящее время никто не знает. Например, сниженность логарифмического пространства и сниженность полиномиального времени эквивалентны тогда и только тогда, когда l = p.

GHMRSS00] Рэймонд Гринлоу, Х. Джеймс Гувер, Сатору Мияно, Уолтер Л. Руццо, Шуджи Ширайши и Такайоши Шудай. Проект параллельных вычислений: объемы I - III, 2000. http://www.cs.armstrong.edu/greenlaw/research/parallel/

PAP94] Кристос Х. Пападимитриу. Вычислительная сложность. Анкет Аддисон-Уэсли, 1994.

Answer 2

Обратите внимание, что если Classity Class $ C $ имеет полную проблему в рамках класса сокращений $ A $, то та же проблема будет завершена для $ C $ Under и класс сокращений, содержащих $ A $.

Обычно доказательства полноты проходят с гораздо более слабым классом сокращений, чем обычно (например, под $ mathsf {ac^0} $ сокращения). Любого класса сокращений, содержащих $ mathsf {ac^0} $, будет достаточно, и есть бесчисленные такие классы.

Вы также можете проверить следующую статью:

• Agrawal, M, Allender, E., Impagliazzo, R., Pitassi, T. и Rudich S., «Уменьшение сложности снижения«Журнал вычислительной сложности, 10, стр.117-138, 2001. Предварительная версия в« Слушаниях ACM Stoc », 2001.

Answer 3

Как отмечает Артем в своем комментарий, Вопрос довольно нельзя, так как вы можете определить все, что вам нравится. Позвольте мне проиллюстрировать, где все начинает быть «немного глупым».

Некоторые обозначения: для двух проблем $ p, q $, написать $ p leq_f q $ для некоторого класса функций $ f $, если есть $ f in f $, так что $ p (x) = q (f (x) ) $ за все входные данные $ x $ ($ p $), то есть, если $ p $ может быть $ f $-уменьшенным до $ Q $. Напишите $ xc_f $ для класса $ x $ -complete Проблемы по отношению к $ f $, то есть

$ qquad displaystyle xc_f = {p in x mid forall q in x. q leq_f p } $.

Кроме того, обозначайте $ t_x $ набор (асимптотически оптимальных) функций времени выполнения алгоритмов, которые вычисляют функции в некоторых наборах $ x $.

Теперь рассмотрим произвольный (сложный) класс проблем $ x $ ¹. Если мы ограничиваем пространство сокращения $ f $ с точки зрения сложности времени - все возможное здесь - есть примерно два случая:

• $ T_f supseteq omega (t_x) $ ² - сокращения не быстрее решателя проблем.

  В этом случае $ xc_f = x $ - это явно не очень интересно для теории сложности. Учитывая, что такое $ f $ может быть полезно на практике, особенно если $ t_f subteq theta (x) $; Вы можете уменьшить все проблемы в $ x $ до нескольких проблем, которые вы можете решить очень хорошо. Линейное программирование и SAT являются типичными примерами из-за высоко оптимизированного LP-соответствующего. SAT-SOSTREVERS.

• $ T_f subteq o (x) $ - сокращения быстрее, чем решающие проблемы

  Здесь могут произойти интересные вещи, то есть $ xc_f submet x $ или $ xc_f neq xc_ {f '} $ для различных пространств для сокращения. Есть ли эти факты интересные последствия, зависит от конкретного выбора $ x $ и $ f $. Обратите внимание, что может произойти $ xc_f = pellyset $, что само по себе достаточно интересно.

  Вещи определенно становятся довольно неинтересными, когда вы выбираете $ f $ так "маленький", что $ leq_f $ является скудным, это может быть мало сокращений. Подумайте о $ x = mathsf {np} $ и $ f $ так, что $ t_f subteq o (n) $; Снижение должно значительно сокращать размеры ввода и не может тратить на него слишком много времени, так что $ f $ не очень мощный.

  Обратите внимание, однако, что даже ограничение на $ t_f subteq o (1) $ оставляет значимые отношения; Например, «$ x $ ровно ровно?» Можно ли уменьшить до "$ x $ первого бита 0?" в $ O (1) $ время и пространство. Таким образом, было бы интересно изучить даже такие слабые сокращения, чтобы выяснить, какие проблемы близки к тому, к чему другие с точки зрения сложности снижения; Вы определенно видите такие различия в классическом $ mathsf {npc} = mathsf {np} c_p $ сокращения.

Технически существует третий случай, например, $ t_f = p $ и $ t_x = theta (n^3) $; В этом случае - если $ f $ разумно богата - комментарии по делу о первом. Также обратите внимание, что вопрос, в какой вопрос $ f $ попадает сама по себе: «$ mathsf {p = np} $?» по сути спрашивает, является ли $ t_f = theta (x) $ (и даже если $ f = theta (xc_f) $).

---

1. Чтобы быть «правильным» классом сложности, он должен быть какой -то «нисходящей закрытой» сложности WRT.
2. $ circ (x) $ для функционального класса $ x $ и $ circ $ a Landau Символ является естественным расширением обычных символов Ландау, то есть $ circ (x) = bigcup_ {f in x} circ (f) $.