Космическая сложность признания Уотсона-Крика Палиндрома

Question

У меня есть следующая алгоритмическая проблема:

Определите сложность пространства, распознавающие строки ДНК, которые являются Watson-Crick Palindromes.

Уотсон-Крик Палиндромы-это строки, чей вспять комплемент-оригинальная строка. А дополнение определяется в виде букв, вдохновленная ДНК: a-это комплемент t и c-комплемент G. Простой пример для WC-палиндрома-ACGT.

Я придумал два способа решения этого.

Один требует $ mathcal {o} (n) $ space.

• После того, как машина закончила читать вход. Входная лента должна быть скопирована на рабочую ленту в обратном порядке.
• Затем машина будет читать входные и рабочие ленты слева и сравнивать каждую запись, чтобы проверить ячейку на рабочей ленте, является комплиментом ячейки на входе. Это требует $ mathcal {o} (n) $ space.

Другое требует $ mathcal {o} ( log n) $ space.

• При чтении ввода. Подсчитайте количество записей на входной ленте.
• Когда входная лента выполняется чтение
  • Скопируйте дополнение буквы на рабочую ленту
  • Скопируйте букву L до конца рабочей ленты
• (Точка петли), если счетчик = 0, очистите рабочую работу и напишите «да», затем остановите
• Если входная лента считывает l
  • Переместите входную головку влево на количество раз, указанное счетчиком (требует второй счетчик)
• Если входная лента считывает r
  • Переместите входную головку вправо на количество раз, указанное счетчиком (требует второй счетчик)
• Если ячейка, которая содержит значение в рабочей тренере, соответствует текущей ячейке на входной ленте
  • уменьшить счетчик на два
  • Переместите один влево или вправо, в зависимости от того, находится ли R или L на рабочем месте соответственно
  • Скопируйте дополнение L или R в рабочую тренажеру вместо текущего L или R
  • Продолжить петлю
• Если значения не совпадают, очистите WorkTape и напишите нет, затем остановите

Это выпускается примерно на 2 доллара log n+2 $ для хранения обоих счетчиков, текущего дополнения и значения L или R.

Моя проблема

Первый требует как линейного времени, так и пространства. Второй требует $ frac {n^2} {2} $ Time и $ log n $ пространство. Мне дали проблему из цитаты и придумали эти два подхода, но я не знаю, с каким из них. Мне просто нужно дать пространство сложность проблемы.

Причина, по которой я смущен

Я хотел бы сказать, что второй - лучший вариант, так как он лучше с точки зрения времени, но этот ответ только от меня повезет и придумывает алгоритм. Похоже, что если я хочу дать пространственному сложности чего -то, это не потребует удачи, чтобы придумать правильный алгоритм. Я что-то упускаю? Должен ли я даже придумать решение проблемы, чтобы ответить на сложность пространства?

Answer 1

Отказ от ответственности: Следующий алгоритм не использует стандартную модель для сложности сублимеровного пространства (см. WP: Dspace), потому что он пишет на входную ленту. Кроме того, набор (Watson-Crick) Palindromes не находится в $ mathsf {dspace} ( mathcal {o} (1)) = mathsf {reg} $. Тем не менее, это решение на месте для многих практических целей (например, если каждая буква char в c).

Чтобы показать, что проблема имеет определенную пространственную сложность, обычно нужно придумать алгоритм, который обладает этой сложностью пространства. Это может потребовать проб и ошибок, но лучший подход состоит в том, чтобы иметь хорошее понимание проблемы, на которую вы рассматриваете, и большой опыт в алгоритмах и сложности.

Для этого конкретного примера существует третий алгоритм, который не нуждается в каком -либо дополнительном пространстве и требует сложности $ O (n^2) $. Этот алгоритм будет постоянным пространством.

Подсказка: Зачем использовать дополнительное пространство, когда вы можете использовать пространство, занятое входом?

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

Answer 2

Как задается вопрос, вы должны придумать верхняя граница и нижняя граница на пространственной сложности.

Первая часть обычно выполняется путем представления алгоритма для вашей проблемы, но сокращение к Некоторая другая хорошо изученная проблема также будет работать (и косвенно даст алгоритм). Поскольку вы не рассматриваете комбинированную сложность (время и пространство) только пространство имеет значение, даже если время увеличивается. Таким образом, вы нашли верхнюю границу $ mathcal {o} ( log n) $.

Вторая часть, как правило, намного сложнее, но вы можете легко показать, что постоянного пространства недостаточно, потому что это сделало бы ваш язык регулярным. Используя насосную лемму с, скажем, $ a^lb^{2l} a^l $, где $ l $ является предполагаемым номером для насоса. Это все еще оставляет большой разрыв между $ omega (1) $ и $ mathcal {o} ( log n) $.

Я нашел упражнение (См. Упражнение 6) который дает некоторые подсказки. Если я правильно интерпретаю их подсказки, попробуйте доказать, что есть много разных классов эквивалентности отношения Myhill-Dnerode для каждого входного размера. Это похоже на аргумент, что вы не можете различить более чем $ c cdot gamma^{s (n)} $ строки длины $ n $ (где $ gamma $ - это ваш алфавит ленты и $ s (n) $ ваша космическая сложность). Это даст вам более низкую границу $ omega ( log n) $.

---

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

Answer 3

Крайне вероятно, что классический Просмотр пространства для палиндромов Удерживает также в вашем случае. В этом результате говорится, что машина Тьюринга, распознавая палиндромы в пространстве $ s $, должна занять время $ omega (n^2/s) $, то есть $$ textrm {time} times textrm {space} = omega (n^ 2). $$ В вашем случае, первый алгоритм имеет $ ts = theta (n^2) $, а второй имеет $ ts = theta (n^2 log n) $. Можно также показать, что нижняя граница для пространства - $ omega ( log n) $. Я не смог найти то, что является лучшей верхней границей - то есть есть ли алгоритм с использованием логарифмического пространства и времени $ o (n^2/ log n) $, или в целом, для каких значений $ S $ мы можем достичь времени $ omega (n^2/s) $. В качестве упражнения вы можете попытаться найти другие гибридные алгоритмы, интерполирующие два ваших алгоритма.