Наследственный класс структур (например, графы) - это класс, замкнутый при индуцированных подструктурах или, что то же самое, замкнутый при удалении вершины. Классы графов, которые исключают минор, имеют хорошие свойства, которые не зависят от конкретного исключенного минора. Мартин Грох показал,...
Заранее извиняюсь, если этот вопрос слишком прост. По сути, я хочу знать, есть ли какие-либо функции со следующими свойствами:е( х )е(Икс)f(x) Возьмем как когда домен и кодомен ограничены битными строками. потомf ( x ) nеN( х )еN(Икс)f_n(x)е( х )е(Икс)f(x)NNn еN( х )еN(Икс)f_n(x) инъективен еN( х...
Это продолжение этого вопроса и связано с этим вопросом Шивы Кинали. Кажется, что доказательства в этих работах ( Аллендер , Кауссин-Маккензи-Териен-Фольмер , Койран-Перифель ) используют теоремы иерархии. Я хочу знать, являются ли доказательства « чистыми » теоремами диагонализации или они...
Есть две основные, изученные теории лямбда-исчисления, теория бета и его Постполное расширение, теория бета-эта. Есть ли в этих двух теориях промежуточное, некое промежуточное правило, которое дает теорию переписывания слияния? Есть ли какое-то интересное понятие частичной экстенсиональности,...
Я всегда заинтригован отсутствием численных доказательств в экспериментальной математике за или против вопроса P против NP. В то время как гипотеза Римана имеет некоторые подтверждающие данные из численной проверки, я не знаю аналогичных доказательств для вопроса P против NP. Кроме того, мне...
Естественное доказательство является препятствием для доказательства нижних оценок сложности схемы булевых функций. Они напрямую не подразумевают такого барьера в доказательстве нижних границ сложности схемы. Есть ли прогресс в выявлении таких барьеров? Есть ли другие барьеры в монотонной...
Преобразование Уолша-Адамара (WHT) является обобщением преобразования Фурье и представляет собой ортогональное преобразование для вектора действительных или комплексных чисел размерности . Преобразование популярно в квантовых вычислениях, но недавно оно было изучено как своего рода предварительное...
В презентации 2006 года под названием EXPANDER GRAPHS - ОСТАЮТСЯ ЛИ какие-то ТАЙНЫ? Нати Линиал поставил следующую открытую проблему: Какие трудные вычислительные задачи на графе остаются сложными, когда они ограничены графами расширителей?NпNпNP С тех пор был ли достигнут какой-либо прогресс в...
Савич дал детерминированный алгоритм для решения проблемы st-связности, используя пространство , подразумевая . Алгоритм Савича выполняется за время . Это большая открытая проблема, может ли st-связность быть решена детерминированным алгоритмом за полиномиальное время и в O ({\ log} ^ 2 {n})...
В статье Разборова-Рудича « Естественные доказательства» , стр. 6, в той части, в которой они обсуждают, что есть «сильные доказательства нижних границ против моделей монотонных схем» и как они вписываются в картину, есть следующие предложения: Здесь проблема не в конструктивности - все свойства,...
Это -трудного найти постоянный коэффициент приближение длинного цикла в кубических гамильтоновых графах. Кубические гамильтоновы графы имеют как минимум два гамильтоновых цикла.NпNпNP Каковы наиболее известные верхняя и нижняя границы числа гамильтоновых циклов в кубических гамильтоновых графах?...
ΣИксΠi j ∈ Eе( хя, хJ)∑x∏ij∈Ef(xi,xj)\sum_x \prod_{ij \in E} f(x_i,x_j)МаксимумИксΠi j ∈ Eе( хя, хJ)maxx∏ij∈Ef(xi,xj)\max_x \prod_{ij \in E} f(x_i,x_j) Где max или сумма берется по всем меткам VVV , произведение берется по всем ребрам ЕEE для графа G = { V, E}G={V,E}G=\{V,E\} а еff - произвольная...
3-реберная раскраска кубических графов является полной. Теорема о четырех цветах эквивалентна «Любые кубические плоские безмостовые графы раскрашиваются по 3 ребрам»NпNпNP Какова сложность 3-реберной раскраски кубических плоских графов? Также предполагается, что раскраска -edge является NP- трудной...
Этот вопрос может быть задан либо в рамках сложности схем булевых схем, либо в рамках теории алгебраической сложности, либо, вероятно, во многих других ситуациях. Подсчитав аргументы, легко показать, что на N входах существуют булевы функции, для которых требуется экспоненциально много гейтов...
Пусть и два двоичных числа с битами и двоичное число (длина ) произведения и . Мы хотим вычислить наиболее значимый бит произведения .уИксxxYyyz = x ⋅ y 2 n x y z 2 n - 1 z = z 2 n - 1 … z 0NnnZ= х ⋅ у z=x⋅y z = x \cdot y\ 2 н2n2nИксxxYyyZ2 n - 1z2n−1z_{2n-1}Z= z2 n - 1… З0z=z2n−1…z0z = z_{2n-1}...
Я заинтересован в генерации псевдослучайных чисел для криптографии. Помимо главы 5 Менезес / Oorschot / Vanstone ; Глава 8 Стинсона ; и глава 3 Goldreich , где еще я могу найти больше? Меня интересуют общие принципы проектирования PRNG (желательные свойства, тесты и т....
Мой вопрос общий: как мне начать думать с точки зрения разработки и сложности алгоритмов? Я собираюсь пройти аспирантуру по разработке алгоритмов. Я зарегистрировался в нем раньше, но бросил его позже, потому что не мог идти в ногу с этим. Я должен принять этот курс как требование. Есть ли уловка,...
Пытаясь разработать собственный алгоритм сортировки, я ищу оптимальный эталон, с которым я могу его сравнить. Для несортированного порядка элементов A и отсортированного порядка B , какой эффективный способ вычислить оптимальное количество транспозиций, чтобы добраться от A до B ? Транспонирование...
Одним из классических расширений проблемы максимального потока является проблема «максимального потока во времени»: вам дается орграф, два узла которого различаются как источник и приемник, где каждая дуга имеет два параметра, - единичное время и задержка. Вы также дали горизонт времени . Цель...
Мы часто рассматриваем классы сложности, где мы ограничены количеством пространства, которое может использовать наша машина Тьюринга, например: или NSPACE ( f ( n ) ) . Похоже, что в начале теории сложности были достигнуты большие успехи с этими классами, такими как теорема о пространственной...