Единая иерархия задач, которые охватывают сложность и вычислительные иерархии

Кто-нибудь знает о наборе проблем, которые единообразно варьируются и охватывают одну из «интересных» иерархий сложности и вычислимости? Под интересным я имею в виду, например, полиномиальную иерархию, арифметическую иерархию или аналитическую иерархию. Или, может быть (N) P, (N) EXP, 2 (N) EXP, $\ldots$

Более конкретно: вы можете задать единый набор задач, которые характеризуют арифметическую иерархию: . Но они не всегда являются наиболее полезными для сведения к актуальным проблемам. $0, 0', \overline{0'}, 0'', \overline{0''},\ldots$

С другой стороны, в книге Харела, Козена и Тиурина есть ряд различных задач, связанных с : NP, $\Pi^0_1$ , $\Sigma^0_2$ и $\Sigma^1_1$ завершены. Проблемы полезны для демонстрации сокращений, но не совсем понятно, будут ли они обобщаться равномерно, чтобы охватить другие уровни иерархий, в которых они находятся.

Кто-нибудь знает такой набор конкретных, единообразных проблем, которые охватывают иерархию?

РЕДАКТИРОВАТЬ: Просто для пояснения, я знаю, что три иерархии, которые я даю, прежде всего, имеют стандартные определения с точки зрения переменного уровня квантификатора. Это не то, что я ищу. Я ищу что-то другое, например, игру на графике или головоломку, в которую играют мозаики.

cc.complexity-theory computability Марк Рейтблатт
источник

Существуют проблемы, основанные на графике (например, достижимость), и проблемы, основанные на логике (оценка схемы или формула первого порядка). ps: вы пытались создать игру между двумя игроками с определенным количеством раундов или ограниченной вычислительной мощностью? Кстати, это может помочь, если вы поясните, что вы подразумеваете под словами «униформа» и «бетон».

Каве

Да, есть проблемы с графиком или схемой, которые имеют вариации для пары уровней. Но можете ли вы найти аналоги, полные для всех уровней иерархии? Под униформой я подразумеваю, что, чтобы подняться в иерархии, вы просто меняете какой-то параметр каким-то единообразным способом. Например, вы увеличиваете число X на единицу, где X - некоторый параметр проблемы. Под конкретным я просто неофициально имею в виду доступность. Я не считаю иерархии проблемы остановки особенно доступными. С другой стороны, что-то вроде SAT или QBF является более конкретным.

Марк Рейтблатт

Продолжая комментарии Каве: такой язык, вероятно, также будет p-изоморфным TQBF, если только кто-то не планирует доказать, что гипотеза Бермана-Хартманиса об изоморфизме неверна на некотором (или на каждом) уровне PH. В этом случае это будет очень тонкая маскировка, поскольку это будет просто перекодировка TQBF, то есть вы записали количественные пропозициональные формулы, используя другое булево кодирование.

Джошуа Грохов

@Mark: у меня нет хорошей интуиции для гипотезы об изоморфизме. Оригинальная статья BH предполагает, что это может быть правдой; Затем Джозеф и Янг предположили, что односторонние функции могут показать, что это ложно (в основном: применить одностороннюю функцию к SAT, чтобы получить NP-полный набор, который, вероятно, не изоморфен SAT), но затем Роджерс показал релятивизированные миры, реализующие все четыре возможности: существование односторонних функций и гипотеза об изоморфизме. Так что я не знаю, есть ли действительно консенсус в данный момент. Вот статья Роджерса: dx.doi.org.proxy.uchicago.edu/10.1006/jcss.1997.1486

Джошуа

(Статья Джона Роджерса, по-видимому, примерно на 2 года позже, чем обсуждение в блоге CC, но я не знаю точной истории того, когда он получил результат, в отличие от того, когда он был впервые опубликован.)

Джошуа Грохов,

[Построение понимания Каве в комментариях.] Кажется маловероятным, чтобы кто-то мог придумать семейство проблем, которое значительно отличается от количественной булевой формулы, не опровергнув PH-аналог гипотезы изоморфизма Бермана-Хартманиса. Без этого любая проблема, с которой вы столкнетесь, будет не только эквивалентной , но и фактически изоморфной ей. Один из способов определения изоморфизма между двумя языками здесь состоит в том, чтобы взять один абстрактный язык, но кодировать его объекты (в данном случае, количественные логические формулы), используя два различных логических кодирования. $QBF_k$

С другой стороны, изоморфизм не обязательно является хорошим суждением о том, что людям полезно выдвигать доказательства. В конце концов, в арифметической иерархии теорема Майома об изоморфизме доказывает арифметический аналог гипотезы об изоморфизме ЧД (фактически, это история в обратном направлении, так как ЧМ был мотивирован Михиллом). Тем не менее, как указывает вопрос, существует несколько «разных» характеристик разных уровней, некоторые из которых более полезны для доказательств, чем другие.

Хотя кажется маловероятным, чтобы кто-либо придумал такое единое семейство языков для каждого уровня PH, в двух опросах ( один , два ), проведенных Шефером и Умансом, обсуждаются естественные проблемы, которые, по крайней мере, «отличаются» от QBF для первых нескольких уровни PH.

Джошуа Грохов
источник

Хорошая связь с BH. :)

Kaveh

Единая иерархия задач, которые охватывают сложность и вычислительные иерархии

Ответы: