Я думал, что поделюсь этим вопросом, так как он может быть интересен для других пользователей здесь. Предположим, что функция из однородного класса (например, ) также входит в небольшой неоднородный класс (например, A C 0 / p o l y , т. Е. Неоднородный A C 0 ), означает ли это, что функция...
Предполагается, что поскольку обратное подразумевает \ mathsf {PH} = \ Sigma_2 . Теорема Ладнера устанавливает, что если \ mathsf {P} \ ne \ mathsf {NP}, то \ mathsf {NPI}: = \ mathsf {NP} \ setminus (\ mathsf {NPC} \ cup \ mathsf {P}) \ ne \ emptyset , Однако доказательство, по-видимому, не...
Я хочу знать, помогает ли неравномерность вычислительным функциям на практике. Легко показать, что в есть функции, возьмем любую невычислимую функцию и рассмотрим язык { }, который явно имеет простые неоднородные схемы , но не вычисляется равномерно, но это не тот тип функций, который меня...
Теорема Карпа – Липтона утверждает, что если , то P H разрушается до Σ P 2 . Следовательно, при условии разделения между Σ P 2 и Σ P 3 , никакая N P -полная проблема не будет принадлежать P / p o l y .N P ⊂ P / p o l yNP⊂P/poly\mathsf{NP} \subset \mathsf{P/poly}P...
Язык находится в если существует машина Тьюринга для пространства журналов, которая решает язык с полиномиальным количеством рекомендаций.Л / р о л уL/поLYL/poly Смотрите здесь для получения дополнительной информации: https://en.wikipedia.org/wiki/L/poly Вопрос Каковы последствия ?п⊆L / p o l...
Учитывая алгоритм, работающий во время , мы можем преобразовать его в «тривиальное» однородное семейство цепей для той же самой задачи размера не более .≈ t ( n ) log t ( n )t(n)t(n)t(n)≈t(n)logt(n)≈t(n)logt(n)\approx t(n)\log t(n) С другой стороны, может случиться так, что у нас есть гораздо...
P/poly=NP/polyP/poly=NP/polyP/poly = NP/poly означает , что, в свою очередь, имеет интересные последствия, такие как коллапс полиномиальной иерархии.NP⊆P/polyNP⊆P/polyNP \subseteq P/poly Есть ли интересные последствия для ?P/poly≠NP/polyP/poly≠NP/polyP/poly \neq...
Помощник преподавателя курса сумел написать программу, которая (детерминистически) генерирует сложные экзаменационные вопросы. Теперь она хотела бы написать программу, которая генерирует соответствующие ответы. Проблема Ревизора спрашивает, всегда ли это возможно; в ГИПОТЕЗА экзаменатора утверждает...
Общий вопрос Обобщает ли теорема о пространственной иерархии неравномерное вычисление? Вот несколько более конкретных вопросов: Является ли ?L / ролу⊊ PSпA CЕ/ РолуL/poly⊊PSPACE/polyL/poly \subsetneq PSPACE/poly Для всех космических построимых функций , является D S Р С Е ( О ( е ( п ) ) ) / р о л...
Под BPP / linear я подразумеваю машины BPP с линейным советом, который выполняет обещание, когда дается «правильный» совет, и дерандомизация должна дать нам, скажем, P / линейный или (SUBEXP / линейный) алгоритм. Если мы используем неоднородные предположения, я думаю, классические результаты должны...
Этот вопрос возник в контексте криптографии, но ниже я представлю его с точки зрения теории сложности, поскольку здесь люди больше знакомы с последним. Этот вопрос связан с проблемами в NP, но не в Average-P / poly и неоднородности биения по Oracle Access . Неформальное утверждение: когда...
Я думал о следующем вопросе в разное время с тех пор, как увидел этот вопрос по криптографии . Вопрос Позволять рRRбыть отношением TFNP . Может ли случайный оракул помочь П / поли сломаться?рRRс ничтожной вероятностью? Более формально, \newcommand{\Pr}{\operatorname{Pr}}...
Мне любопытно, как вы видели неоднородность полезной в вычислениях. Одним из способов является случайность, как вBPP⊆P/polyВпп⊆п/поLYBPP \subseteq P/polyи другой - это справочные таблицы, которые используются, чтобы показать, что все языки имеют неоднородные схемы. В частности, меня интересуют...