Почему мы рассматриваем лог-пространство как модель эффективных вычислений (вместо полилог-пространства)?

49

Это может быть субъективный вопрос, а не конкретный ответ, но в любом случае.

В теории сложности мы изучаем понятие эффективных вычислений. Существуют классы, такие как обозначает полиномиальное время , а обозначает пространство журнала . Оба они считаются своего рода «эффективностью», и они довольно хорошо отражают трудности некоторых проблем.LPL

Но есть разница между и : в то время как полиномиальное время, , определяется как объединение задач, которое выполняется за время для любой постоянной , это,L P O ( n k ) kPLPO(nk)k

P=k0TIME[nk] ,

пространство журнала определяется как . Если мы подражаем определению , оно становитсяS P A C E [ log n ] PLSPACE[logn]P

PolyL=k0SPACE[logkn] ,

где называется классом пространства полилогов . Мой вопрос:PolyL

Почему мы используем пространство журнала как понятие эффективного вычисления, а не пространство полилога?

Одна главная проблема может быть о полных наборах проблем. При сокращении пространства журнала «один-один» у и есть полные проблемы. Напротив, если имеет полные проблемы при таких редукциях, то мы бы противоречили теореме о пространственной иерархии. Но что, если мы перешли к сокращению полилога? Можем ли мы избежать таких проблем? В общем, если мы стараемся вписать в понятие эффективности и (при необходимости) изменить некоторые определения, чтобы получить все хорошие свойства, которые должен иметь «хороший» класс, как далеко мы можем зайти?PLPolyLPolyL

Есть ли теоретические и / или практические причины для использования пространства журнала вместо пространства полилога?

Сянь-Чжи Чан 張顯 之
источник
Сянь-Чи, Хороший вопрос.
Мухаммед Аль-Туркистани
9
Известно , что . Насколько я лично знаю, точная связь между и неясна. , возможно, что некоторые проблемы в разрешимы, а в и наоборот - не разрешимы . (Это на самом деле частично говорит о вашем вопросе о том, почему является странным кандидатом для понятия эффективных вычислений.) Чтобы больше о , вы можете к учебнику по сложностям Papadimitriou , в частности к упражнениям и обсуждению в конце главы 16.Р р о л у л р о л у л П р о л у л р о л у LpolyLPPpolyLpolyLP polyLpolyL
Даниил
На самом деле, еще один быстрый комментарий о незначительной части вашего общего вопроса: Полилог сокращение пространства не расскажет вам много о , по тем же причинам полиномиальные сокращения времени не сказать вам много о . PpolyLP
Даниэль Апон
@Daniel Apon: Спасибо, что упомянули книгу, и это приятно :) Для второго комментария по тому же аргументу мы можем использовать линейные сокращения вместо полиномов, чтобы получить больше информации о , верно? P
Сянь-Чжи Чанг 之 之
Чи Чанг: Ну, я не знаю о сокращении линейного времени на говорят, но есть и другие, интересные представления о сокращениях , которые дают информацию о сложности внутри . P
Даниэль Апон

Ответы:

51

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

Лэнс Фортноу
источник
4
Это выглядит как лучший ответ на заданный вопрос.
Деррик Стоули
1
Из всех этих хороших ответов, я думаю, что ответ Ланса - самый точный, и я приму его. Но все равно большое спасибо каждому продуманному ответу!
Сянь-Чи Чанг 之 之
1
Кроме того, является открытой проблемой, является ли P = L.
Диего де Эстрада
25

Одна из проблем заключается в том, что неизвестно, . Это в значительной степени убивает понятие эффективности. С другой стороны, определение того, является ли пересечение языков, распознаваемых автоматами непустыми, является при сокращениях пространства журналов [Ланге-Россманит] . Возможно, есть некоторые похожие проблемы для детерминированного полилопространства.log k - 1 ( n ) NSPACE [ log k n ] -полныйSPACE[log2n]Plogk1(n)NSPACE[logkn]-complete

Класс изучался в прошлом. [Кук] доказал, что . Как отметил Деррик Столи, этот класс теперь известен как и обобщен в . Больше информации здесь .PLOSS=kTISP[nk,klog2n]DCFLPLOSSSC2SCk

Майкл Блондин
источник
2
Можем ли мы использовать вместо ? QuasiP=k0TIME[2logkn]P
Сянь-Чи Чанг 之 之
Это известная открытая проблема? Не могли бы вы предоставить ссылку?
Мухаммед Аль-Туркистани
Ваш класс PLOSS такой же, как в современных терминах. SC означает «класс Стива», вероятно, для того результата Кука, который вы цитируете. SC2
Деррик Стоули
5
Обратите внимание, что SC был назван Ником Пиппенгером в предположительно взаимной договоренности со Стивом Куком, чтобы назвать NC в его честь :)
Suresh Venkat
так же это правильно: так как является ОЧЕНЬ важным классом, представляющим эффективность, поэтому вместо изменения с на , чтобы соответствовать , мы используем чтобы соответствовать ? Тогда, если через какое-то время отношение будет доказано для некоторого , станет ли класс более важным? PPQuasiPpolyLLPSPACE[logkn]PkLk
Сянь-Чи Чанг 之 之
20

Пространство журнала гарантирует полиномиальное время, поскольку существует не более конфигураций данной машины Тьюринга для пространства журналов. Полные проблемы Undirected Reach и Directed Reach (для L и NL соответственно) очень «хороши» для размышления.2O(logn)=poly(n)

Обратите внимание, что ваше определение PolyL также дает PolyL = NPolyL по теореме Савича, поскольку .NSPACE[logkn]SPACE[log2kn]

Когда речь идет о пространстве полилогов, была проделана работа по рассмотрению пространства полилогов с одновременным полиномиальным временем, давая иерархию SC: . SCk=TISP[poly(n),logkn]

Деррик Стоули
источник
Если вместо этого мы используем сокращения полилогов, станет ли достижимость полной проблемой для ? (Я так думаю, с помощью того же метода достижимости, который доказывает достижимость как -полная проблема). Если это так, по-прежнему «хорош» в некотором смысле. Н L р ø л у LpolyLNLpolyL
Сянь-Чи Чанг 之 之
Если вы используете сокращение Polylog для задач PolyL, язык является PolyL-полным. {1}
Деррик Стоули
Вы правы, извините за глупый вопрос :(
Сянь-Чи Чанг 之 之
13

Я думаю, что все остальные ответы очень хороши; Я постараюсь дать другой взгляд на проблему.

Я не знаю, насколько хорошо P моделирует «эффективные» вычисления в реальном мире, но нам нравится класс из-за его хороших свойств замыкания и других математических причин. Точно так же L - хороший класс по некоторым из вышеупомянутых причин.

Однако, как вы прокомментировали, если мы снизим наше определение «эффективного» до квазиполиномиального времени, то PolyL также будет эффективным. Мы могли бы обсудить теорию сложности, где мы позволяем классам, определенным с логарифмической границей на некотором ресурсе, вместо этого использовать ресурсы полилога. Соответственно, мы также ослабили бы наши определения NC, NL и т. Д., Чтобы вместо этого допустить схемы квазиполиномиального размера. Если мы сделаем это, NC 1 , L, NL и NC все совпадут с классом PolyL. В этом смысле PolyL является устойчивым классом, поскольку многие естественные классы совпадают с ним. Для получения дополнительной информации о теории сложности с log -> polylog и полиномиальной -> квазиполиномиальной, см. Классы схем квазиполиномиального размера по Barrington.

Другая причина изучения polyL или аналогичных классов, таких как квази-AC 0, заключается в том, что хотя разделение оракула между (скажем) ParityP и PH подразумевает, что PARITY не содержится в AC 0 , обратное следствие неизвестно, чтобы быть правдой. С другой стороны, PARITY не содержится в квази-AC 0 тогда и только тогда, когда существует разделение оракула между ParityP и PH. Точно так же классы квази-TC 0 и квази-AC 0 различны тогда и только тогда, когда между CH и PH существует разделение оракула. Таким образом, обычные классы сложности, такие как PH, ModPH, CH и т. Д. При уменьшении экспонентой для доказательства результатов оракула, превращаются в квазиполиномиальные версии обычных классов AC 0 , ACC 0 и TC.0 соответственно. Точно так же аргумент, используемый в теореме Тоды (PH содержится в P PP ), может использоваться, чтобы показать, что квази-AC 0 содержится в квази-TC 0 глубины-3 . (Я не знаю, известен ли такой же вывод для обычных версий этих классов. В некоторых статьях я видел это в списке открытых проблем.)

Робин Котари
источник
1
Ваш ответ действительно помогает, спасибо, что поделились своим мнением. Я поражен, что квази-что-то было изучено много!
Сянь-Чи Чанг 之 之