Я ищу полный текст результата клики Луны и Мозера 1965 г. О кликах в графах (существуют графы с числом максимальных клик, экспоненциальным по ). Платежная система моего университета не имеет доступа к конкретному журналу. (На самом деле, предварительный просмотр предоставляет первые несколько...
Я ищу в Интернете доступные лекционные заметки или другие ресурсы, которые дают хорошее введение в параллельное программирование, подобно параллельным аналогам базовых классов по информатике. Я сосредоточен на следующем: пока я могу говорить о «разделяй и властвуй», жадных алгоритмах, динамическом...
Существует ли алгоритм полиномиального времени, чтобы найти - если он существует - остовный паук данного графа ? Паук - это дерево с не более чем одним узлом со степенью больше 2: я знаю, что различные условия степеней на (по существу, достаточно большие степени узлов) гарантируют существование...
Алгоритм Дойча является хорошо известным квантовым вычислением f(0)+f(1)mod2f(0)+f(1)mod2f(0) + f(1)\mod{2} только с одной оценкой fff . Если мы заменим +++ на ⋅⋅\cdot проблема, похоже, станет другой. Мой вопрос: существует ли квантовый алгоритм, вычисляющий значение f(0)⋅f(1)f(0)⋅f(1)f(0)\cdot...
В поисках исследовательских работ о системах типов для императивных языков я нахожу решения только для языка с изменяемыми ссылками, но без подлинных императивных структур управления, таких как составные операторы, циклы или условные выражения. Поэтому не ясно, как можно реализовать императивный...
Я довольно хорошо знаком с теорией, лежащей в основе VC-Dimension, но сейчас я смотрю на последние (последние 10 лет) достижения в теории статистического обучения: (локально) средние Радемахера, лемма о конечных классах Массарта, Покрывающие числа, Цепочки, Дадли Теорема, псевдоразмерность,...
Пусть граф с (положительно) взвешенными ребрами. Я хочу определить диаграмму Вороного для набора узлов / сайтов S , чтобы связать с узлом v ∈ S подграф R ( v ) группы G, индуцированный всеми узлами строго ближе к v, чем к любому другому узлу в S , измеряя длина пути по сумме весов на дугах. R ( v )...
Каков современный уровень сложности запросов для правильных формул PAC, изучающих 2-DNF с типовыми запросами и при равномерном распределении ? Или какие-нибудь нетривиальные ограничения на это? Поскольку я совсем не знаком с теорией обучения, и этот вопрос мотивирован другой областью, ответ может...
Какова текущая наилучшая граница для выполнения запросов подсчета диапазона полупространства для набора мерных точек, выраженного в форме компромисса времени / пространства. Согласно основополагающей работе Матусека 1993 года (теорема 6.2, Поиск диапазона с эффективными иерархическими вырезами), мы...
В статье « О двух проблемах теории информации» Эрдёс и Реньи дают нижние оценки минимального количества взвешиваний, которое необходимо сделать, чтобы определить количество фальшивых монет в наборе из монет.NNn Более формально: Поддельные монеты имеют меньший вес, чем правильные монеты; веса и как...
JBV предложил мне превратить некоторые комментарии в вопрос, так что здесь. Другой вопрос [1] касается применения QM-вычислений. Одним из ответов [2] было «эффективное моделирование квантовой механики». Очевидно, эта идея восходит к ранним работам Фейнмана на эту тему; хотя у меня нет ссылки. Так:...
Несколько лет назад я наткнулся на следующее левое правило равенства в последовательном исчислении: s≐t⇝θθ(Γ)⊢θ(C)Γ,s≐t⊢Cs≐t⇝θθ(Γ)⊢θ(C)Γ,s≐t⊢C \frac{s \doteq t \leadsto \theta \qquad \theta(\Gamma) \vdash \theta(C)} {\Gamma, s \doteq t \vdash C} Здесь s≐t⇝θs≐t⇝θs \doteq t \leadsto \theta вычисляет...
Пусть некоторое множество Взаимно несмещенной баз (MUB) в С п , т.е. каждый B я ортонормированный базис и V ∈ B я , ш ∈ B J , я ≠ J мы есть | ⟨ V | ж ⟩ | = 1B={B1,…,Bk}B={B1,…,Bk}\mathcal{B} = \{B_1, \dots, B_k\}CnCn\mathbb{C}^nBiBiB_iv∈Bi,w∈Bj,i≠jv∈Bi,w∈Bj,i≠jv \in B_i, w \in B_j, i \neq j . Мы...
В простейших представлениях для графов используются матрицы / списки смежности, что означает, что каждый узел и ребро представлены явно. Важность неявных представлений для графов, демонстрирующих сильные закономерности, давно признана. Например, Galperin & Wigderson (1983), Papadimitriou &...
Пусть . Мне нужно сгенерировать простые графы G обхвата g , чтобы множество всех g- циклов образовывало двойное ребро, покрывающее G (то есть каждое ребро делится ровно двумя g- циклами), и такое, чтобы пересечение любых двух g- циклы - это либо вершина, ребро, либо пустое. Сгенерированные графы...
Недавно я прочитал приличное количество статей CoLT. Хотя я не борюсь с отдельными статьями (по крайней мере, не больше, чем я обычно борюсь с другими теоретическими работами), я не чувствую, что у меня есть хорошее широкое понимание области в целом. Существуют ли стандартные тексты, обзоры или...
Я ищу ссылки на сложность проблемы балансировки булевых формул . В частности, Было ли известно, что булевы формулы могут быть сбалансированы в ?AC0AC0\mathsf{AC^0} Есть ли простое доказательство балансировки булевой формулы в ?AC0AC0\mathsf{AC^0} Под «простым» я подразумеваю доказательство, более...
Я пишу магистерскую диссертацию по CS и работаю с анализом псевдонимов. То, что меня интересует, - это внутрипроцедурный, чувствительный к потоку анализ обязательных и возможных псевдонимов для подобных Java языков. Я ищу тексты, которые подробно описывают основы этого предмета, но не смогли найти...
Я слышал о результате в приблизительной окраске графика, но не могу найти источник. Результат: Для каждой константы существует достаточно большое k, такое, что раскраска k- раскрашиваемого графа в h k цветов NP-трудна.часhhКkkКkkч кhkhk Может ли кто-нибудь указать мне соответствующую...
Учитывая направленный граф, мы хотим решить, содержит ли он направленный цикл четной длины. В этой статье 1997 года, написанной YUSTER и ZWICK, утверждается, что проблема не в том, что она находится в а также в том, что она не является N P -полной.ппPNпNпNP Есть ли какой-либо недавний результат,...