Вопросы с тегом «relativization»

63
Больше о PH в PP?

Недавний вопрос по Гека Bennett с просьбой , был ли класс PH содержится в классе РР, получил несколько противоречивые ответы (все это правда, кажется). С одной стороны, несколько результатов оракула были даны наоборот, а с другой Скотт предположил, что ответ, вероятно, положительный, так как...

28
Существуют ли канонические нерелятивизирующие методы?

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

22
Есть ли в теории вычислимости результат, который не релятивизируется?

Я читал статью Андрея Бауэра « Первые шаги в теории синтетической вычислимости» . В заключении он отмечает, что Наша аксиоматизация имеет свой предел: она не может доказать какие-либо результаты в теории вычислимости, которые не могут относиться к вычислениям оракула. Это так, потому что теория...

18
Какова «реальная» причина того, что IP = PSPACE является нерелятивизирующим?

ООOC ø N P O ⊆ P S P C E O Oc o N PОP я PОсоNпО⊈япО{\sf coNP}^O \not\subseteq {\sf IP}^Oc o N PО⊆ Р С Р С ЕОсоNпО⊆пSпAСЕО{\sf coNP}^O \subseteq {\sf PSPACE}^OООO Тем не менее, я видел только несколько человек, которые дают «прямое» объяснение того, почему результат не релятивизируется, и обычный...

18
Можно ли проверить, является ли вычислимое число рациональным или целым?

Можно ли алгоритмически проверить, является ли вычисляемое число рациональным или целым? Другими словами, возможно ли для библиотеки, которая реализует вычислимые числа, предоставлять функции isIntegerили isRational? Я предполагаю, что это невозможно, и что это как-то связано с тем, что невозможно...

17
Что такое оракул минимальной сложности, который отделяет PSPACE от полиномиальной иерархии?

Фон Известно , что существует оракул такое , что .P S P A C E A ≠ P H AAAAPSPACEA≠PHAPSPACEA≠PHAPSPACE^A \neq PH^A Даже известно, что разделение справедливо относительно случайного оракула. Неофициально можно интерпретировать это как означающее, что существует много оракулов, для которых и...

16
Потенциально равные классы сложности без известных противоречивых релятивизаций

Какие примеры пар классов сложности и B такие, чтоAAABBB мы не знаем, является ли , иA=BA=BA=B мы также не знаем противоречивых релятивизаций (т. е. мы не знаем оракулов и Q таких, что A P = B P и A Q ≠ B Q )?PPPQQQAP=BPAP=BPA^P = B^PAQ≠BQAQ≠BQA^Q \ne B^Q Чтобы сформулировать вопрос по-другому,...

15
Поддержание порядка в списке в за раз

Задача обслуживания заказа (или «поддержание заказа в списке») заключается в поддержке операций: singleton: создает список с одним элементом, возвращает указатель на него insertAfter: дает указатель на элемент, вставляет новый элемент после него, возвращает указатель на новый элемент delete: дает...

15
Релятивизируют ли доказательства того, что перманент не является равномерным

Это продолжение этого вопроса и связано с этим вопросом Шивы Кинали. Кажется, что доказательства в этих работах ( Аллендер , Кауссин-Маккензи-Териен-Фольмер , Койран-Перифель ) используют теоремы иерархии. Я хочу знать, являются ли доказательства « чистыми » теоремами диагонализации или они...

13
ALogTime! = PH трудно доказать (и неизвестно)?

Лэнс Фортноу недавно заявил, что доказательство L! = NP должно быть проще, чем доказательство P! = NP : Отдельный NP от логарифмического пространства. Я дал четыре подхода в обзоре диагонализации перед разделом 2001 года (Раздел 3), хотя ни один из них не удался. Должно быть намного проще, чем...

13
Каковы естественные примеры нерелятивизируемых доказательств?

Насколько я понимаю, доказательство того, что P = NP или P ≠ NP, должно быть нерелятивизируемым (как в оракулах теории рекурсии). Практически все доказательства кажутся релятивизируемыми. Какие хорошие примеры , не являющиеся Релятивизуемых доказательств, из тех , что Р = NP / P ≠ NP доказательству...

12
Можно ли использовать результаты релятивизации для доказательства формально независимых предложений?

Можно ли продемонстрировать, что предложение должно быть формально независимым, основываясь на том факте, что оно нерелятивизирующее? Другими словами, есть ли в предложениях теории вычислимости / сложности примеры предложений, где можно продемонстрировать, что а) что все доказательства, которые...

11
Руццо-Симон-Томпа Механизм доступа оракула

NL⊈PNL⊈P\mathsf{NL} \nsubseteq \mathsf{P} Теперь рассмотрят схему семьи с оракулом воротами - скажем, , где классе сложности схемы , содержащая logspace с доступом оракула к другому классу , через оракул ворот приложенного к основанию . Существуют ли какие-либо патологические примеры, похожие по...

11
Релятивизированный мир, где

Я хотел бы знать , если существует Релятивизированные мир , где . Я также интересно знать , если существует Релятивизированные мир , где P B ≠ N P B = P P B .пA= N PA≠ P PAпAзнак равноNпA≠ппA{\bf P^A}={\bf NP^A}\not = {\bf PP^A}пВ≠ N PВ= P PВпВ≠NпВзнак равноппВ{\bf P^B} \not = {\bf NP^B} = {\bf...

11
Охватывает ли диагонализация суть разделения классов?

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

10
Результаты Oracle на P против BPP

Позвольте быть любой полной проблемой EXP. Тогда Р = Н Р .AAAпA= NпAPA=NPAP^A = NP^A Пусть некоторый оракул , который принимает на счета запросов, М (а ТМ Р) будут делать, и мы можем получить P B ≠ N P B .ВBBMMMпВ≠ NпВPB≠NPBP^B \neq NP^B Вопрос: есть ли у нас аналогичные результаты оракула для P...

10
Миры, относительно которых «неуязвимые генераторы» не существуют

Неуязвимые генераторы определяются следующим образом: Пусть RRR - отношение NP, а MMM - машина, которая принимает L(R)L(R)L(R) . Неформально программа является неуязвимым генератором, если на входе 1n1n1^n она создает пары свидетельства экземпляра (x,w)∈R(x,w)∈R(x, w) \in R , где |x|=n|x|=n|x| = n...

9
Может ли случайный оракул изменить, какие проблемы с TFNP сильно усугубляются?

Я думал о следующем вопросе в разное время с тех пор, как увидел этот вопрос по криптографии . Вопрос Позволять рRRбыть отношением TFNP . Может ли случайный оракул помочь П / поли сломаться?рRRс ничтожной вероятностью? Более формально, \newcommand{\Pr}{\operatorname{Pr}}...