Пусть GGG - общий оракул в смысле категории Коэна / Бэра. Пусть RRR случайный оракул. Существуют ли классы сложности A и B с AG=BGandAR≠BRAG=BGandAR≠BR\mathrm{A}^G=\mathrm{B}^G\quad\text{and}\quad\mathrm{A}^R\ne \mathrm{B}^R или наоборот,...
У меня есть проблема, которая находится в NEXP и также может быть решена с помощью чередующегося ТМ, использующего экспоненциальное время и только одно чередование (начиная с экзистенциального состояния).NPNP^{\text{NP}} Что-нибудь известно о NEXP ? Это равно NEXP или какому-то другому классу?...
Я не помню, чтобы видел разделение классов, не основанное на диагонализации и результатах релятивизации. Диагонализация все еще может использоваться для разделения оставшихся известных классов, потому что нерелятивизирующие аргументы могут все еще использоваться в заключении диагонализации или в...
Как можно взглянуть на проблему и причину, по которой это скорее NP-Intermediate, чем NP-Complete? Часто довольно просто взглянуть на проблему и сказать, является ли она NP-Complete или нет, но мне кажется, что гораздо сложнее определить, является ли проблема NP-Intermediate, так как грань между...
Я предполагаю, что это назвали бы # P-Space, но я нашел только одну статью, смутно упоминающую это. Как насчет подсчета версий EXP-TIME-Complete, NEXP-Complete, а также проблем EXP-SPACE-Complete? Есть ли какие-либо предыдущие работы, которые можно привести в отношении этого или любого типа...
Ответ: неизвестно Большое спасибо всем, кто помог уточнить этот вопрос и определения, связанные с ним. Определения этой вики послужили отправной точкой для более новой вики TCS: « Содержит ли P языки, существование которых не зависит от PA или ZFC? (Вики сообщества TCS) ». Более поздняя вики...
NL⊈PNL⊈P\mathsf{NL} \nsubseteq \mathsf{P} Теперь рассмотрят схему семьи с оракулом воротами - скажем, , где классе сложности схемы , содержащая logspace с доступом оракула к другому классу , через оракул ворот приложенного к основанию . Существуют ли какие-либо патологические примеры, похожие по...
Является ли Н ПP P= PP PNPPP=PPP\mathsf{NP^{PP}} = \mathsf{P^{PP}} ? Или, в более общем плане , Is Н ПP P⊆ PP P/ РолуNPPP⊆PPP/poly\mathsf{NP^{PP}} \subseteq \mathsf{P^{PP}/poly}
Известно , что некоторые (не релятивизованных) синтаксические классы сложности между и P S P A C E имеют следующее свойство, P ⊆ C O N P ⊆ U S ⊆ C = P ⊆ P P ⊆ P S P C E , Мне интересно, существует ли (нерелятивизированный) синтаксический класс сложности X такой, что P P ⊆ X ⊆ P S P A C EпP{\bf P}P...
Класс UP определяется так: Класс решения задач, решаемых машиной NP, такой, что Если ответ «да», принимается ровно один путь вычислений. Если ответ «нет», все пути вычислений отклоняются. Я пытаюсь развить интуицию для этого определения. Можно ли сказать, что проблемы UP - это проблемы с...
Я думал о том, к какому классу принадлежит этот язык: - граф, - натуральное число, а - хроматическое числоL = { ⟨ G , к ⟩ | GLзнак равно{⟨грамм,К⟩|граммL =\{ \langle G,k \rangle \mid G ККkККkG }грамм}G\} Я думал о как (1) «нет раскраски k-1 цветов» и (2) «есть раскраска цветов». Теперь (1) - это...
Какие есть доказательства того, что ?c o R P≠ NпcoRP≠NPcoRP \neq NP c o R PcoRPcoRP - это класс языков, для которых существует вероятностная машина Тьюринга, которая работает за полиномиальное время и всегда отвечает Да на входе, принадлежащем языку, и отвечает Нет с вероятностью, по крайней мере,...
Известен ли какой-либо класс сложности, содержащий онлайн-аналоги задач оптимизации? Если нет, то как можно определить такой класс? Мы знаем, что у многих проблем есть онлайн-версия: например, онлайн-версия проблемы с упаковкой бункера. Проблемы онлайн сложнее, если судить по их...
Интересно знать погоду есть редкий язык (даже построен с задержкой diagolanization) в НПИ в предположении , что .P≠NPP≠NPP \neq
В этом вопросе было отмечено, что существуют версии описательной сложности теоремы Райса. Я нашел доказательство следующей теоремы: Учитывая класс сложности C , нетривиальные свойства языков в C не могут быть вычислены в C Ранее я опубликовал найденное мной доказательство, но поскольку оно было...
Язык входит в класс если есть два языка и такие чтоD P L 1 ∈ N P L 2 ∈ c o N P L = L 1 ∩ L 2LLLД ПDPDPL 1 ∈ NпL1∈NPL1 \in NPL 2 ∈ c o NпL2∈coNPL2 \in coNPL = L 1 ∩ L 2L=L1∩L2L = L1 \cap L2 Канонической -полной проблемой является SAT-UNSAT: учитывая два выражения 3-CNF, и , верно ли, что выполнимо,...
Гипотеза Бермана – Хартманиса: все NP-полные языки выглядят одинаково в том смысле, что они могут быть связаны друг с другом полиномиальными изоморфизмами времени [1]. Меня интересует более мелкозернистая версия «полиномиального времени», то есть, если мы используем параметризованные сокращения....
BPPBPP\mathsf{BPP} иZPPZPP\mathsf{ZPP} - два основных класса вероятностной сложности. BPPBPP\mathsf{BPP} - это класс языков, определяемых вероятностными алгоритмами Тьюринга за полиномиальное время, где вероятность возврата неправильного ответа ограничена, т. Е. Вероятность ошибки не...
Класс сложности определяется следующим образом (из Википедии ):Sп2S2P\textrm{S}_2^\textrm{P} Язык находится в S P 2, если существует предикат P полиномиального времени, такой чтоLLLSп2S2PS_2^PпPP Если , то существует такой y , что для всех z , P ( x , y , z ) = 1x ∈ Lx∈Lx \in LYyyZzzп( х , у, z) =...
Если мы можем доказать, что , означает ли это, что ?L=PL=P\mathsf{L}=\mathsf{P}NL=NPNL=NP\mathsf{NL}=\mathsf{NP} Я думал, что это так, но я не могу доказать это (также для