Язык в NSPACE (O (n)) и, скорее всего, не в DSPACE (O (n))

10

На самом деле я обнаружил, что набор контекстно-зависимых языков, ( принятых языков) не так широко обсуждается, как (обычные языки) или (контекстно-свободные языки). А также открытая проблема не так известна, как «аналогичная» проблема: « ".CSLR E G C F L D S P A C E ( O ( n ) ) = ? N S P A C E ( O ( n ) ) P = ? Н П=NSPACE(O(n))=LBAREGCFLDSPACE(O(n))=?NSPACE(O(n))P=?NP

Ну есть ли действительно такая аналогия?

  1. Есть ли язык в который не может быть доказан в (например, полные языки)?D S P A C E ( O ( n ) ) N PCSLDSPACE(O(n))NP
  2. Более того: существует ли язык в который является «полным» в следующем смысле: если мы можем доказать, что находится в мы получаем, что ?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 ) )LCSLLDSPACE(O(n))DSPACE(O(n))=NSPACE(O(n))
  3. (Может быть, просто вопрос мнения) Находятся ли обе проблемы на одном уровне сложности?
rl1
источник
L против является более аналогичной проблемой, чем против . П Н ПNLPNP
rus9384
Я думаю, что вы получили достаточно хорошие ответы; Вы можете принять один. Если эти два ответчика не знают, вопрос, вероятно, открыт. Не стесняйтесь переиздавать на « Теоретической информатике», если считаете, что это полезно, но, пожалуйста, не забудьте дать ссылку сюда, чтобы люди не тратили свое время на написание одних и тех же вещей.
Рафаэль

Ответы:

8

Более известной версией этих вопросов является вопрос . Если то (немного хитрый) аргумент заполнения показывает, что , и поэтому подразумевает известную гипотезу .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 ) LN LL=?NLL=NLDSPACE(n)=NSPACE(n)DSPACE(n)NSPACE(n)LNL

Гипотеза считается (некоторыми) более доступной, чем гипотеза . Я не уверен, что многие люди имеют мнение о гипотезе .PN P D S P A C E ( n ) N S P A C E ( n )LNLPNPDSPACE(n)NSPACE(n)

Более общая картина здесь заключается в том, является ли теорема Савича , которая гласит, что для разумного , туго. Хотя , я думаю, что большинство людей считают, что . С другой стороны, я не уверен, что люди считают, что - оптимальный взрыв; возможно, меньший показатель также работает, по крайней мере, в некоторых случаях. Смотрите, например, недавний Arxiv бумагу , спараметрированное пространство сложность модель проверки ограниченной логики переменного первого порядка , по Yijia Чена, Майкл Эльберфельде и Moritz Мюллер.т ( п ) лог н Н Р С Р С Е = Р С Р С Е Н С Р A C E ( n k ) D S PNSPACE(t(n))DSPACE(t(n)2)t(n)lognNPSPACE=PSPACEt ( n ) 2NSPACE(nk)DSPACE(nk)t(n)2

Юваль Фильмус
источник
Это помогает увидеть связанные проблемы. Спасибо за это.
rl1
Вы сказали: «Я не уверен, что многие люди имеют мнение относительно гипотезы ». Но гипотеза все еще является предметом исследования, не так ли? DSPACE(n)NSPACE(n)
17
Если под этим вы подразумеваете предмет активного исследования, я не уверен. Но наверняка будет интересно (для сообщества) узнать ответ.
Юваль
Почему аргумент заполнения сложен? Если , не означает ли это, что DTM нужно пространство для имитации NTM? O ( log n )L=NLO(logn)
rus9384
@ rus9384 Попробуйте на самом деле запустить аргумент, чтобы увидеть сложность, или посмотрите на ссылку.
Юваль
1
  1. Да, для сокращений DSPACE (O (n)) существуют полные CSL- языки . В основном все еще вариант направленной достижимости, который может быть ограничен ациклической достижимостью, если это необходимо.
  2. Да, смотрите 1.
  3. Вы имеете в виду, вопрос 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)

    Даже после того, как мы поймем, должны ли мы верить , доказать это, вероятно, будет так же невозможно, как доказать . Райан Уильямс приводит одну явную причину и говорит:PN PLNLPNP

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

    ответить ALogTime! = PH трудно доказать (и неизвестно)? Ланс Фортноу в основном поднял вопрос и все еще не согласен. Мой собственный урок был:

    Это означает, что утверждение «ALogTime! = PH» - это как раз то место, где начинаются трудности с доказательством результатов разделения. Можно отметить, что это утверждение фактически эквивалентно «ALogTime! = NP», поскольку «ALogTime = NP» подразумевает «P = NP = PH».

Томас Климпел
источник
Спасибо! Это ответило бы на все мои вопросы, но я не понимаю ваш ответ 1. st-связность (достижимость) в ориентированных графах является проблемой -complete ( NL-complete ). Не могли бы вы объяснить, что вы подразумеваете под «вариантом» (или дать ссылку)? NL
rl1
@ rl1 Кодировка ориентированного графа отличается, и особенно его размер равен O (exp (n)). В основном график переходов соответствующей машины Тьюринга (с фиксированным пределом памяти).
Томас Климпел
У вас есть ссылка для точного определения вашего варианта и для "полного" доказательства?
rl1
@ rl1 Я проверил несколько вводных книг по теории сложности. Лечение в Пападимитриу по этой теме хорошее и подробное, лечение в Арора / Барак также достаточно хорошее. Менее уверены, даст ли лечение в Sipser или Goldreich то, что вы хотите. Пападимитриу также имеет смысл, потому что это старая книга, и это старая тема, а также потому, что тема кодирования графов переходов с помощью подходящих ограниченных машин Тьюринга также появляется в новых исследованиях Пападимитриу.
Томас Климпел
Пападимитриу («Вычислительная сложность», 1995) дает упражнение (стр. 67) и теорему о том, что «REACHABILITY является -полным (стр. 398)». Но это не отвечает на мои вопросы, поэтому, к сожалению, я не смог найти результат, который вы упомянули в своем ответе в 1. и 2.CSL=NSPACE(n)NL
rl1
1

В добавление к другим ответам, существует понятие приводимости и полноты для проблемы CSL против DCSL, а именно, сводимость по лог-линии, и есть вполне естественные проблемы, полные CSL. Например, проблема неэквивалентности для регулярных выражений. Вот очень похожий на ваш вопрос вместе с ответом, содержащим дополнительную информацию и ссылки: /cstheory/1905/completeness-and-context-sensitive-languages

Герман Грубер
источник
-1

SATNTIME(n)DSPACE(n)L=PNPDSPACE(n)DSPACE(n)L=NLDSPACE(n)=NSPACE(n)в результате применения аргумента заполнения. Поскольку когда то строго содержится в . Тем не менее, и, следовательно, и, следовательно, не может быть случая, чтобы какая то проблема была в потому что это означало бы противоречие с которое мы получили после предположения .L=NLL=PNPNSPACE(n)CSL=NSPACE(n)CSLNPCSLcompleteNPCSLNPL=P

Кроме того, вы можете увидеть возможную попытку доказать здесь:L=P

https://hal.archives-ouvertes.fr/hal-01999029

Фрэнк Вега
источник