На самом деле я обнаружил, что набор контекстно-зависимых языков, ( принятых языков) не так широко обсуждается, как (обычные языки) или (контекстно-свободные языки). А также открытая проблема не так известна, как «аналогичная» проблема: « ".R E G C F L D S P A C E ( O ( n ) ) = ? N S P A C E ( O ( n ) ) P = ? Н П
Ну есть ли действительно такая аналогия?
- Есть ли язык в который не может быть доказан в (например, полные языки)?D S P A C E ( O ( n ) ) N P
- Более того: существует ли язык в который является «полным» в следующем смысле: если мы можем доказать, что находится в мы получаем, что ?C S L L D S P A C E ( O ( n ) ) D S P A C E ( O ( n ) ) = N S P A C E ( O ( n ) )
- (Может быть, просто вопрос мнения) Находятся ли обе проблемы на одном уровне сложности?
Ответы:
Более известной версией этих вопросов является вопрос . Если то (немного хитрый) аргумент заполнения показывает, что , и поэтому подразумевает известную гипотезу .L = N L D S P A C E ( n ) = N S P A C E ( n ) D S P A C E ( n ) ≠ N S P A C E ( n ) L ≠ N LL=?NL L=NL DSPACE(n)=NSPACE(n) DSPACE(n)≠NSPACE(n) L≠NL
Гипотеза считается (некоторыми) более доступной, чем гипотеза . Я не уверен, что многие люди имеют мнение о гипотезе .P ≠ N P D S P A C E ( n ) ≠ N S P A C E ( n )L≠NL P≠NP DSPACE(n)≠NSPACE(n)
Более общая картина здесь заключается в том, является ли теорема Савича , которая гласит, что для разумного , туго. Хотя , я думаю, что большинство людей считают, что . С другой стороны, я не уверен, что люди считают, что - оптимальный взрыв; возможно, меньший показатель также работает, по крайней мере, в некоторых случаях. Смотрите, например, недавний Arxiv бумагу , спараметрированное пространство сложность модель проверки ограниченной логики переменного первого порядка , по Yijia Чена, Майкл Эльберфельде и Moritz Мюллер.т ( п ) ≥ лог н Н Р С Р С Е = Р С Р С Е Н С Р A C E ( n k ) ≠ D S PNSPACE(t(n))⊆DSPACE(t(n)2) t(n)≥logn NPSPACE=PSPACE t ( n ) 2NSPACE(nk)≠DSPACE(nk) t(n)2
источник
Вы имеете в виду, вопрос DSPACE (O (n)) = ? NSPACE (O (n)) на том же уровне сложности, что и вопрос P = ? НП ? Ну, у нас есть веские основания полагать, что P является строгим подмножеством NP , но я не знаю аналогично хорошо разработанных причин полагать, что DSPACE (O (n)) является строгим подмножеством NSPACE (O (n)) , Позвольте мне сосредоточиться на более простом вопросе . Случайные блуждания "неплохи" для изучения (в отношении достижимости) неориентированных графов, связанных с SL O ( log n ) O ( log n )L=?NL , Очевидное тривиальное аналогичное случайное блуждание по ориентированному графу плохо сработает при исследовании ориентированного графа (относительно достижимости). Но, возможно, есть и другие подобные рандомизированные способы исследования ориентированного графа (или слоистого ациклического графа). Исходя из теоремы Савича, я бы даже предположил, что есть такие способы, если мы хотим сохранить изменяющийся набор позиций в ориентированном графе в процессе случайного исследования. И тогда задача состоит в том, чтобы понять, не позволит ли сохранение менее чем позиций провести хорошее рандомизированное исследование.O(logn) O(logn)
Даже после того, как мы поймем, должны ли мы верить , доказать это, вероятно, будет так же невозможно, как доказать . Райан Уильямс приводит одну явную причину и говорит:P ≠ N PL≠NL P≠NP
ответить ALogTime! = PH трудно доказать (и неизвестно)? Ланс Фортноу в основном поднял вопрос и все еще не согласен. Мой собственный урок был:
источник
В добавление к другим ответам, существует понятие приводимости и полноты для проблемы CSL против DCSL, а именно, сводимость по лог-линии, и есть вполне естественные проблемы, полные CSL. Например, проблема неэквивалентности для регулярных выражений. Вот очень похожий на ваш вопрос вместе с ответом, содержащим дополнительную информацию и ссылки: /cstheory/1905/completeness-and-context-sensitive-languages
источник
Кроме того, вы можете увидеть возможную попытку доказать здесь:L=P
https://hal.archives-ouvertes.fr/hal-01999029
источник