Сравнение конечных автоматов: теория сложности

[Профессор Снэйп]

Даны два недетерминированных конечных автомата. Требуется определить, распознают эти автоматы один и тот же язык или они распознают разные языки.

По сложности задача экспоненциальна (строим для каждого автомата эквивалентный ему детерминированный за экспоненциальное время, затем минимизируем детерминированные автоматы за полиномиальное от их объёма время и сравниваем минимальные автоматы). Хочу спросить у тех, кто знает: является ли описанная задача (сравнение языков, распознаваемых НКА) NP-задачей или нет?

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

[Xaositect]

В Гэри-Джонсоне написано, что обе задачи PSPACE-полны.

[Профессор Снэйп]

А PTIME строго включается в PSPACE или нет? Или это неизвестно?

-- Пт окт 09, 2009 00:32:22 --

Или я какую-то глупость написал сейчас?

-- Пт окт 09, 2009 00:36:25 --

Что такое вообще это PSPACE. Полиномиальная память?

Я почему-то полагал, что эта задача требует экспоненциальной памяти. Для каждого натурального $n$ легко придумать НКА с $n$ состояниями, такой что эквивалентный ему ДКА имеет не менее $2^n$ состояний. Получается, что память для записи ДКА растёт экспоненциально от объёма входа (начального НКА). Хотя, конечно, нам ведь надо просто сравнить два ДКА; возможно, их для этого не обязательно будет полностью хранить в памяти.

[Xaositect]

Профессор Снэйп в сообщении #250186 писал(а):

Что такое вообще это PSPACE. Полиномиальная память?

Да.

Есть еще результат, что эквивалентность регулярных выражений с квадратами (допускается операция $R^2 = RR$) требует экспоненциальной памяти.

Там в Гэри-Джонсоне ссылки есть, можно посмотреть, как доказывается.