L / P / PSpace против P / NP

12

в 1979 году Хопкрофт / Ульман написал, что L ⊆ P ⊆ NP ⊆ PSpace известно, но L ⊊ PSpace является единственным известным (и тривиальным) сдерживанием, известным, хотя все предполагаются как надлежащие сдерживания, и «где вещи все еще стоят» ~ 4 десятилетия спустя ,

с тех пор существует ли какая-либо известная связь (и) между L ⊊ P, P ⊊ PSpace и P ⊊ NP? все они все еще считаются независимыми, или есть какие-то признаки какой-то взаимозависимости?

мотивация: этот вопрос частично вдохновлен недавними результатами Backurs-Indyk, связывающими SETH с O (n 2 ) расстоянием редактирования. SETH - экспоненциальное время, а расстояние редактирования - PTime. (а также несколько вопрос о доказательстве нижних границ, доказывая верхние оценки )

ВЗН
источник

Ответы:

8

LPSPACE

Недавняя работа над «Мелкозернистой сложностью», как и результат редактирования расстояния Backurs и Indyk, обходит стороной тот факт, что мы не можем доказать правильное сдерживание, например, . В частности, SETH намного сильнее гипотеза, чем , более или менее утверждая, что CNF-SAT требует времени (не просто супер-полиномиальное время). При этой более сильной гипотезе, если вы можете показать сокращение от CNF- SAT к проблемам в (например, Edit Distance), затем вы получаете условную нижнюю границу основанную на SETH. Таким образом, различия, с которыми связаны эти работы (т.е. противPNPPNP2n2n/kPΩ(nk)2n2(1δ)n) намного жестче, чем различия между традиционными классами сложности, упомянутыми в посте.

Аналогично, при проверке нижних границ схемы с помощью более быстрых алгоритмов выполнимости нам, как правило, нужны только мелкозернистые улучшения по сравнению с тривиальными алгоритмами , чтобы дать нижние оценки. Например, алгоритм для CircuitSAT на схемах с воротами доказал бы .2 n p o l y ( n k ) / n ω ( 1 ) n k N E X P P / p o l yO(2n)2npoly(nk)/nω(1)nkNEXPP/poly

палиндром
источник
Как это отвечает на вопрос, который спрашивает о последствиях (или «взаимозависимости», что бы это ни значило) между тремя утверждениями?
Андрас Саламон,
Я стремился ответить на вопрос, основываясь на его заявленной мотивации. Я лично не осведомлен о каких-либо нетривиальных "взаимозависимостях" между утверждениями.
палиндром