Вы заявили, что можете доказать, что 3 и 5 не находятся в зоне NPDA. Возьми оттуда. Вы переходите к следующему, NP. Здесь вы работаете с машинами Тьюринга с различными ограничениями.
Я могу распознать язык 3 в линейном времени с логарифмическим пространством. Подсчитайте символы. Подсчитайте символы b. Подсчитайте символы c. Сравните количество. Это линейное сканирование данных плюс сравнение двоичных чисел (которое меньше линейного времени для длины ввода). Линейное время является подмножеством NP. Насколько подробно ваш профессор потребовал бы от вас (т. Е. Вам нужно явно ввести третий символ алфавита, чтобы разделить ваши счета? Вам нужно разобрать, как сравнивать двоичные числа?)?
Чтобы решить 5, вам нужно знать границы двоичного умножения. Посчитайте a, посчитайте b, посчитайте c. Умножьте количество a на количество b. Сравните результат с подсчетом c. Это линейное сканирование входных данных плюс сложность бинарного умножения (но помните, что умножаемые вами числа являются log (n) битами). Поскольку ваша зона не очень ограничительна, скажем, по крайней мере, мы связаны полиномиальным временем. Так как P является подмножеством NP, мы здесь.
Чуть выше этого, и я ожидаю, что вы получите более многословное описание проблем. Я предполагаю, что PSPACE находится в вашей зоне EXPTIME, и каноническим примером, который приходит на ум, является количественная логическая формула. Это похоже на SAT (теорема Кука доказывает, что SAT NP-Hard), но с квантификаторами. Есть хорошее доказательство того, что QBF является завершенным PSPACE, что вполне аналогично теореме Кука. Я предполагаю, что ваши контекстно-зависимые языки, которые явно не принадлежат подмножеству в другой зоне, также относятся сюда (на случай, если вы получите описание производственного правила языка).
Следующая зона - это машины Тьюринга, которые останавливаются. Если вы можете описать алгоритм, независимо от того, насколько нелепым (а он должен быть нелепым, или он был бы пойман предыдущей зоной), он может остановиться здесь.
Следующая зона посвящена теореме Райс. Вики этот плохой мальчик. Все доказательства снова просты с теоремой Райс. Эта зона проще, чем придумывать регулярное выражение или FSA для первой зоны.