Есть ли кандидат на естественную проблему в ?

27

Я хочу знать, помогает ли неравномерность вычислительным функциям на практике. Легко показать, что в есть функции, возьмем любую невычислимую функцию и рассмотрим язык { }, который явно имеет простые неоднородные схемы , но не вычисляется равномерно, но это не тот тип функций, который меня интересует.f 0 f ( n ) : n ωP/polyPf0f(n):nω

Есть ли функция, которую мы знаем, что она может быть вычислена неравномерно, но мы не знаем, может ли она быть вычислена равномерно (или хотя бы доказательство того, что она не может быть вычислена равномерно, не очевидно)?

Как можно использовать неоднородность схем для вычисления функций, которые, как известно, не могут быть вычислены равномерно (с почти одинаковым количеством ресурсов)?

Пожалуйста, обратите внимание, что я не хочу патологических функций, таких как невычислимые, упомянутые выше, я хочу естественные функции, которые люди действительно интересуют вычислениями, и вполне вероятно, что они могут или могли бы быть вычислены равномерно.

Редактировать: я знаю, что . Поэтому ответ, который не является результатом дерандомизации, для меня более интересен.BPPP/poly

Редактировать 2: Как Андрас Саламон и Цуёси Ито в своих ответах сказали: , и в есть интересные проблемы, о которых неизвестно , что они есть в , поэтому формально они ответили на мои вопросы, но это не помогает с тем, что меня действительно интересует, поскольку причина, по которой они находятся в заключается в возможности жесткого кодирования разреженного языка в схему. Не редкий язык был бы более интересным.S р R сек е Р Р / р о л уSparseP/polySparsePP/poly

Кава
источник
@ Андрас Саламон, @ Цуйоши Ито: Спасибо. Но что меня интересует, так это понять, как неоднородность может помочь в вычислительных функциях. Тот факт, что разреженные языки находятся в , не помогает с этим, они находятся в просто потому, что мы можем «жестко» кодировать их в схему. Я должен был добавить требование к моему вопросу, что "язык не тривиален в ". Р / р о л у Р / р ö л уP/polyP/polyP/poly
Каве

Ответы:

13

Я не знаю, удовлетворяет ли это вашим требованиям, но в блоге Билла Гасарча в июле 2010 года спрашивается о языках в SPARSE ∩NP, которых, как считается, нет в P, приводя пример из теории Рэмси. Любые такие языки принадлежат (P / poly) ∩NP.

В связи с этим для любого языка L ∈NP язык T L = {1 n : L содержит некоторую строку длины n } в TALLY ∩NP ⊆ SPARSE∩NP ⊆ (P / poly) ∩NP. В зависимости от выбора языка L , T L может не иметь явной причины принадлежать к P.

Цуёси Ито
источник
8

Изящно редкая формулировка Цуёси Ито в другом ответе прямо не говорит об этом, но, возможно, стоит указать: любой разреженный язык написан на P / poly. Тогда также любой язык подсчета находится в P / poly (так как каждый язык подсчета редок).

Таким образом, один из способов найти «естественные» языки в P / poly, но не в P, - это поиск «жестких» разреженных языков. Как вы указали, «самыми трудными» являются неразрешимые, когда они кодируются разреженным способом, например, в унарном. В более общем случае, унарно-кодированная версия любого языка вне EXP будет тогда за пределами P. (Если нет, то рассмотрим машину Тьюринга с экспоненциальным временем, которая генерирует унарное кодирование, составленную из машины, которая во времени решает результирующий унар-кодированный язык это полиномиально в унарной кодировке. Это экспоненциально по размеру исходного экземпляра. Общая машина затем работает за экспоненциальное время.) Некоторый удобный язык с 2-EXP-завершением может тогда подойти вам как «естественная» проблема.

Обратите внимание, что редкий теоретико-логический язык Билла Гасарха, похоже, попадает в категорию языков, созданных путем разбора жесткого языка. Если один кодирует экземпляр как тройку двоичных чисел вместо двух одинарных и одного двоичного, то раскраска больше не будет иметь полиномиальный размер, поэтому язык явно не в NP.

Андраш Саламон
источник
6

Это больше похоже на комментарий в ответ на пересмотренный вопрос (редакция 3), чем на ответ, но он слишком длинный для комментария.

Простое исключение разреженных языков недостаточно для исключения таких языков, как { x ∈ {0,1} * : | x | ∈ S } вместо {1 n : nS }, где S - бесконечное подмножество {0, 1, 2,…}. Я хотел бы отметить, что может быть трудно провести различие между случаем, когда язык принадлежит P / poly, потому что он «по существу редок» (такой как {1 n : nS } и { x : | x | ∈ S}) и случай, когда язык принадлежит P / poly по другим причинам. Проблема здесь, очевидно, состоит в том, как определить термин «по существу разреженный».

Возможно, вы захотите определить «существенную разреженность» следующим образом: язык по существу редок, если его сводить к разреженному языку. Однако необходимо соблюдать осторожность, потому что если в этом определении вы используете сводимость Тьюринга за полиномиальное время, определение эквивалентно членству в P / poly!

Таким образом, очевидная вещь, которую стоит попробовать - это использовать многозначную сводимость за полиномиальное время. Я не знаю, эквивалентно ли это членству в P / poly, не говоря уже о том, содержит ли P / poly какой-либо естественный язык, который в этом смысле существенно не редок.

Цуёси Ито
источник
На самом деле я подумал об этом, когда увидел ответы перед изменением вопроса, так как было естественно думать о булевой комбинации редких языков. Я думал, что исключая языки, которые сводятся к редким языкам (или, может быть, немного больше), должно быть достаточно для моего вопроса, но кажется, что это более сложное, чем я думал. AC0
Каве
@Kaveh: Это может быть еще одним хорошим определением для «по существу разреженного». Читая ваш комментарий, мне интересно, P / poly = P∪ (AC0 / poly) (я думаю, нет), потому что любая проблема в (P / poly) ∖ ( Можно утверждать, что P∪ (AC0 / poly)) «вычислим, используя неоднородное семейство схем полиномиального размера, реально объединяя мощность схем полиномиального размера и мощность неоднородности».
Цуёси Ито
Возможная проблема с моим определением на основе одного из ваших примеров , является ли язык следующие является по существу скуден : проверить , если число единиц на входе в редком языке . (В более общем смысле, пусть будет полной функциональной проблемой для класса сложности а - разреженным языком. Представьте, что имеет большой диапазон, аналогичный функции NumOnes. Пусть - множество s st )f C S f L x f ( x ) SSfCSfLxf(x)S
Каве
[продолжение] Другой класс языков: возьмите разреженный язык и язык полный для класса сложности а затем рассмотрите конкатенацию ( - это где каждый символ заменяется двумя его копиями. например, 010 становится 001100). Можно также требовать, чтобы длина второй части в конкатенации была меньше, чем длина первой части. Эти языки удовлетворяют всем условиям, кроме естественной проблемы, которую люди действительно заинтересованы в решении. A C L = A .01 . S A ASACL=A.01.SAA
Каве
@Kaveh: Хм, я вижу. Спасибо, что поделились примерами. Я отказываюсь от идеи просмотра (P / poly) ∖ (P∪ (AC0 / poly)) как «P / poly по нетривиальным причинам». Если я не ошибаюсь, оба ваших примера представляют собой многозначное многочленное время, приводимое к Это довольно скудный язык, поэтому все еще есть надежда, что определение «существенной редкости», которое я предложил в ответе, может быть подходящим.
Цуёси Ито