Я пытаюсь понять сложность функций, которые можно выразить через пороговые элементы, и это привело меня к . В частности, мне интересно, что в настоящее время известно об обучении в , так как я не эксперт в этой области.TC0TC0\mathsf{TC}^0TC0TC0\mathsf{TC}^0 На данный момент я обнаружил, что: Все из...
Следующая проблема появляется в списке Ааронсона « Десять полуградовых вызовов для теории квантовых вычислений» . IsB Q P = B P PB Q N CВQпзнак равноВппВQNС\mathsf{BQP}=\mathsf{BPP}^{\mathsf{BQNC}} р о л у л о г (п) В В Р В Р Р Б В Н С Другими словами, может ли «квантовая» часть любого квантового...
Я читал, что целочисленное линейное программирование разрешимо за полиноминальное время, если число переменных фиксировано, т.е. n ∈ O ( 1 ) . Если число переменных растет логарифмически, т. Е. N ∈ O ( log 2 ( N ) ) для заданного входного значения размера N , проблема все еще разрешима за...
Какие примеры пар классов сложности и 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 Чтобы сформулировать вопрос по-другому,...
Отказ от ответственности: я очень мало знаю о теории сложности. Извините, но на самом деле нет способа задать этот вопрос, не будучи (ужасно) лаконичным: Какими должны быть морфизмы в «категории» машин Тьюринга? Это, очевидно, субъективно и зависит от толкования теории, поэтому в идеале ответ на...
Мой студент недавно задал следующий вопрос: D T I M E ( f ( n ) ) ⊊ D T I M E ( g ( n ) ) . DTIME(f(n))⊊DTIME(g(n)).DTIME(f(n)) \subsetneq DTIME(g(n)).h ( n ) h(n)h(n)D T I M E ( f ( n ) ) ⊊ D T I M E ( h ( n ) ) ⊊ D T I M E ( g ( n)) ) ?DTIME(f(n))⊊DTIME(h(n))⊊DTIME(g(n))?DTIME(f(n)) \subsetneq...
Теорема Савича показывает, что для всех достаточно больших функций , и доказательство того, что это тесно, является открытой проблемой на протяжении десятилетий ,NSPACE(f(n))⊆DSPACE(f(n)2)NSPACE(f(n))⊆DSPACE(f(n)2)\mathrm{NSPACE}(f(n)) \subseteq \mathrm{DSPACE}(f(n)^2)fff Предположим, мы подходим к...
Мы знаем (на данный момент около 40 лет, спасибо Адлеману, Беннету и Джиллу), что включение BPP P / poly и еще более сильное BPP / poly P / poly имеют место. «/ Poly» означает, что мы работаем неравномерно (отдельная схема для каждой входной длины ), в то время как P без этой «/ poly» означает, что...
Как называется следующий вариант обложки набора? Для заданного набора S, набора C подмножеств S и целого положительного числа K существуют ли K наборов в C, так что каждая пара элементов S лежит в одном из выбранных подмножеств. Примечание. Нетрудно понять, что эта проблема является NP-полной:...
Учитывая язык L, определенный машиной Тьюринга, который его решает, возможно ли алгоритмически определить, лежит ли L в
Задача P называется в APX, если существует некоторая постоянная c> 0 такая, что для P существует алгоритм аппроксимации за полиномиальное время с коэффициентом аппроксимации 1 + c. APX содержит PTAS (это можно увидеть, просто выбрав любую константу c> 0) и P. APX в NP? В частности, означает...
Наследственный класс структур (например, графы) - это класс, замкнутый при индуцированных подструктурах или, что то же самое, замкнутый при удалении вершины. Классы графов, которые исключают минор, имеют хорошие свойства, которые не зависят от конкретного исключенного минора. Мартин Грох показал,...
Заранее извиняюсь, если этот вопрос слишком прост. По сути, я хочу знать, есть ли какие-либо функции со следующими свойствами:е( х )е(Икс)f(x) Возьмем как когда домен и кодомен ограничены битными строками. потомf ( x ) nеN( х )еN(Икс)f_n(x)е( х )е(Икс)f(x)NNn еN( х )еN(Икс)f_n(x) инъективен еN( х...
Это продолжение этого вопроса и связано с этим вопросом Шивы Кинали. Кажется, что доказательства в этих работах ( Аллендер , Кауссин-Маккензи-Териен-Фольмер , Койран-Перифель ) используют теоремы иерархии. Я хочу знать, являются ли доказательства « чистыми » теоремами диагонализации или они...
Я всегда заинтригован отсутствием численных доказательств в экспериментальной математике за или против вопроса P против NP. В то время как гипотеза Римана имеет некоторые подтверждающие данные из численной проверки, я не знаю аналогичных доказательств для вопроса P против NP. Кроме того, мне...
Естественное доказательство является препятствием для доказательства нижних оценок сложности схемы булевых функций. Они напрямую не подразумевают такого барьера в доказательстве нижних границ сложности схемы. Есть ли прогресс в выявлении таких барьеров? Есть ли другие барьеры в монотонной...
В презентации 2006 года под названием EXPANDER GRAPHS - ОСТАЮТСЯ ЛИ какие-то ТАЙНЫ? Нати Линиал поставил следующую открытую проблему: Какие трудные вычислительные задачи на графе остаются сложными, когда они ограничены графами расширителей?NпNпNP С тех пор был ли достигнут какой-либо прогресс в...
Савич дал детерминированный алгоритм для решения проблемы st-связности, используя пространство , подразумевая . Алгоритм Савича выполняется за время . Это большая открытая проблема, может ли st-связность быть решена детерминированным алгоритмом за полиномиальное время и в O ({\ log} ^ 2 {n})...
В статье Разборова-Рудича « Естественные доказательства» , стр. 6, в той части, в которой они обсуждают, что есть «сильные доказательства нижних границ против моделей монотонных схем» и как они вписываются в картину, есть следующие предложения: Здесь проблема не в конструктивности - все свойства,...
Это -трудного найти постоянный коэффициент приближение длинного цикла в кубических гамильтоновых графах. Кубические гамильтоновы графы имеют как минимум два гамильтоновых цикла.NпNпNP Каковы наиболее известные верхняя и нижняя границы числа гамильтоновых циклов в кубических гамильтоновых графах?...