ПРИМЕЧАНИЕ : вопрос был переформулирован в моих ответах: Предполагая теперь, что мы можем найти самых низких предков родного брата за время , может ли ANN действительно выполняться за ?O(1)O(1)O(1)O(logn)O(logn)O(\log n) Квадро - эффективные пространственные показатели. У меня есть головоломка с...
Хорошо известно, что для классического обучения PAC необходимы примеры , чтобы получить границу ошибки ε whp, где d - это VC-размерность концептуального класса.Ω(d/ε)Ω(d/ε)\Omega(d/\varepsilon)εε\varepsilonddd Известно ли, что примеры нужны в агностическом...
Мне любопытно, если бы кто-то мог порекомендовать какой-нибудь дополнительный материал для более глубокого понимания статьи: « Некоторые результаты и проблемы о квантовых неравенствах типа Белла - Цирельсон ». В частности, кое-что, что может более подробно рассказать о геометрической интерпретации...
В статье с тем же названием, что и у этого вопроса, авторы описывают, как построить неблокирующую линеаризуемую операцию CAS с несколькими словами, используя только CAS с одним словом. Сначала они вводят операцию двойного сравнения-одиночного обмена - RDCSS следующим образом: word_t...
Монотонная формула CNF с m членами на n переменных ( ) - это формула вида , где каждый является ИЛИ некоторого подмножества переменных и находятся в диапазоне от до . f ( x 1 , … , x n ) = ⋀ C i C i x 1 , … , x n i 1 мИкс1, … , ХNИкс1,...,ИксNx_1,\ldots,x_nе( х1, … , ХN) = ⋀ Cяе(Икс1,...,ИксN)знак...
Я читаю превосходный обзорный документ Уотроуса на бумаге по теории квантовой сложности. В нем он заявляет, что было бы удивительно, если бы обнаружилось, что проблема, полная QMA, имеет бессмысленное обещание (т.е. быть языком). Почему это так? Связано ли это с тем фактом, что k-локальная...
Существует ли структура данных w-bit word-RAM с временем O (1) на операцию для следующей задачи ?: Поддерживать набор w-битовых неотрицательных целых чисел, который поддерживает операции добавить (х): добавить х к набору удалить (х): удалить х из набора fingerprint (): вернуть отпечаток набора....
Грубо говоря, сопоставление шаблонов перестановок имеет дело с проблемами следующего вида: При заданных перестановках в S n и в с содержит ли подпоследовательность длины , элементы которой упорядочены по σ ?ππ\piSNSNS_nσσ\sigmaSмSмS_mm ≤ nм≤Nm\leq nππ\pi mττ\tauммmσσ\sigma Например, если и σ = ⟨ 2...
Вот вопрос «следа B», если таковой был. Резюме: первое, о чем я думаю, когда пытаюсь дать семантику недетерминированным программам, приводит к семантике, где я не могу доказать вещи о циклах, которые заканчивают только недетерминированно. Конечно, кто-то определил, что делать в этой ситуации, или,...
Может ли кто-нибудь указать мне на ссылку на неопределяемость модуля функционала непрерывности в PCF? \newcommand{\N}{\mathbb{N}} \newcommand{\bool}{\mathsf{bool}} Андрей Бауэр написал очень хороший пост в блоге, в котором более подробно рассматриваются некоторые вопросы, но я кратко изложу его...
Мой вопрос касается эквивалентности безопасности различных односторонних функций-кандидатов, которые могут быть построены на основе сложности факторинга. Предполагая проблему ФАКТОРИНГ: [Дано для случайных простых чисел , найти , ]P , Q < 2 n P QN=PQN=PQN = PQP,Q<2nP,Q<2nP, Q < 2^nPPPQQQ...
Для смешанного графа с ребрами E и дугами A найдите совпадение в E, которое минимизирует количество дуг в G / M , где G / M получается из G путем сжатия совпадающих вершин и удаления параллельные дуги.G=(V,E,A)G=(V,E,A)G=(V,E,A)EEEAAAEEEG/MG/MG/MG/MG/MG/MGGG Является ли (вариант решения) этой...
Я хочу начать изучать сетевое кодирование: http://en.wikipedia.org/wiki/Network_coding Знаете ли вы какой-либо хороший опрос (например, из опросов и учебных пособий IEEE) по вышеуказанным предметам. Я нашел несколько университетских курсов в Google, но я хотел бы получить рекомендации от людей,...
Существуют ли должности для недавно выпускников бакалавриата или магистратуры, имеющих опыт исследований, для работы в качестве научного сотрудника, прежде чем приступить к выполнению своей кандидатской диссертации? У TCS есть культура постдоковых должностей для недавних выпускников PhD, чтобы...
Скажем, у нас есть многогранник в стандартной форме: A x = bх ≥0Ax=bx≥0\begin{equation*} \begin{array}{rl} \mathbf{A}\mathbf{x} = \mathbf{b} \\\\ \mathbf{x} \ge 0 \end{array} \end{equation*} Существуют ли какие-либо известные способы нахождения гиперплоскости которая разбивает многогранник таким...
Кац и Линделл упоминают в своей книге, что LFSR были ужасны в качестве основы для псевдослучайных генераторов, и выступают за то, чтобы они больше не использовались (ну, они также рекомендуют людям использовать блочные шифры вместо потоковых шифров). Но я вижу, например, что один из шифров в...
Предположим, что - булев язык из конечных строк над . Пусть будет количеством строк в с длиной . Для функции от натуральных чисел до натуральных чисел имеет верхнюю плотность если для всех достаточно больших .{ 0 , 1 } L n L n d ( n ) L d ( n ) L n ≤ 2 n d ( n ) nLLL{ 0 , 1...
Язык входит в класс если есть два языка и такие что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, и , верно ли, что выполнимо,...
Я столкнулся с довольно сложной дилеммой: Я закончил M.Tech в CS 2 года назад, закончив диссертацию в области VLSI тестирования. Хотя мне нравилась моя работа, я не хочу возвращаться, чтобы продолжить свою докторскую диссертацию в этом - я очень хотел продолжить теоретический курс (в приближении /...
Я ищу полный текст результата клики Луны и Мозера 1965 г. О кликах в графах (существуют графы с числом максимальных клик, экспоненциальным по ). Платежная система моего университета не имеет доступа к конкретному журналу. (На самом деле, предварительный просмотр предоставляет первые несколько...