Я читаю старую статью MC Golumbic о графиках EPT (пересечение ребер в дереве). В статье показано, что число максимальных кликов экземпляра графа EPT является полиномиальным. Он приходит к выводу, что если оракул сообщает, что графггG является графиком EPT, то можно найти максимальную клику с...
DLOGTIME определяется по адресу http://en.wikipedia.org/wiki/DLOGTIME определяется по адресу http://en.wikipedia.org/wiki/L_%28complexity%29 и определены по адресу http://en.wikipedia.org/wiki/NC_%28complexity%29 LL\operatorname{L} Северная КаролинаNC\operatorname{NC}Северная...
Предположим структуру в сложности коммуникации, где у нас есть два игрока A (вши) и B (ob) и R (eferee). А и Б не общаются напрямую друг с другом. В каждом раунде общения каждый из них отправляет сообщение (mAmAm_A, mBmBm_B) в R.R вычисляет две функции fA(mA,mB)fA(mA,mB)f_A(m_A,m_B) а также...
(Извинения, если это неуместно или слишком широко. Я открыт для предложений о том, как это переформулировать.) Я заинтересован в отслеживании "древней" истории алгоритмов максимального потока и алгоритмов дискретной оптимизации в целом. Форд-Фулкерсон мой соломенный стартовый пункт. Каковы были...
Теорема PCP утверждает, что каждая проблема решения в NP имеет вероятностно проверяемые доказательства (или, что то же самое, что существует полная и квази-звуковая система доказательств для теорем в NP, использующая постоянную сложность запроса и логарифмически много случайных битов). «Народная...
Триангуляции Делоне на плоскости максимизируют минимальный угол в треугольнике. Справедливо ли то же самое для триангуляции Делоне точек на сфере? (здесь «угол» - это локальный угол в окрестности вокруг вершины на вершине). Вдохновленный, но не связанный с этим вопросом на...
Я ищу программное обеспечение для вычисления / оценки объема многомерных выпуклых многогранников. В частности, я заинтересован в программе, которая может обрабатывать тела сNNn вершины в dddпространство с параметрами, ограниченными примерно следующим образом: d≤ 50d≤50d \le 50 а также n ≤...
В продолжение этого вопроса ... Я пытаюсь научиться использовать и создавать нейронные сети для своих исследований, и один момент несколько ускользает от меня. Я понимаю, что скрытые слои являются несколько необходимой частью этого, однако я застрял в двух моментах, которые мои ссылки не объясняют...
Предположим, у меня есть список подмножеств . Я могу сделать предварительную обработку в этом списке, если это необходимо. После этой предварительной обработки мне предоставляется другой набор . Я хочу , чтобы определить , какие - либо множества с .XX\cal X{1,...,n}{1,...,n}\{1, ...,...
При интерпретации ключей как натуральных чисел мы можем использовать следующую формулу. h(k)=⌊m(kAmod1)⌋h(k)=⌊m(kAmod1)⌋\begin{equation} h(k) = \lfloor m (kA\bmod{1}) \rfloor \end{equation} Что мне трудно понять, так это то, как мы выбираем значение A, где: 0<A<10<A<1\begin{equation} 0...
Хотелось бы знать, почему для распознавания контекстно-свободных языков работают только недетерминированные автоматы push-down (DPA = NPDA). Почему детерминированные автоматы (DPDA) не распознают такие...
Я хотел выяснить, каковы некоторые применения SGT в области теории информации и кодирования и, возможно, коммуникаций. Самое связанное, что приходит на ум, это работа над кодами расширителей. Майкл Сипсер и Даниэль Спилман, «Коды расширителей», IEEE Transactions по теории информации, том 42, № 6,...
В контексте некоторых недавних работ мы определили язык, основанный на трехзначной логике а-ля Клини, где111 означает истинное, 000 за ложь и ⊥⊥\botза ошибку или не знаю. Чтобы показать, что наш язык выразителен, мы хотели доказать, что мы можем построить функционально завершенный набор операторов....
На поисковые системы все чаще полагаются как на стражу информации, однако критерии, используемые поисковыми системами для ранжирования результатов, непрозрачны для пользователей. Как пользователи могут быть уверены в том, что их результаты не являются предвзятыми или подделаны каким-либо образом,...
Какова возможность для ученого изменить свою область в чистый математик? и какой самый плавный способ сделать это? какие-нибудь примеры для людей, которые могли бы это...
Мой вопрос немного расплывчатый. Мне было интересно, если (и как), мы можем применить понятие ширины дерева для задач упаковки в графах. Я был бы счастлив с любым пониманием или ссылками прошлой исследовательской работы на этом (предполагая, что они - некоторая связь)....
У меня есть вопрос, ответ на который, вероятно, хорошо известен, но я не могу найти ничего значащего после небольшого поиска, поэтому я был бы признателен за некоторую помощь. Мой вопрос заключается в том, известно ли, что решение о том, является ли число трансцендентным, неразрешимо. Возможно,...
Есть ли какие-либо известные результаты о сложности поиска разделителя (любого размера), удовлетворяющего заданному свойству? Я знаю, что разделитель кликов легко найти (за полиномиальное время), а также знаю, что во многих работах рассматривается проблема поиска небольших разделителей или...
Существует линейная программа, для которой я хочу не просто решение, а решение, которое является как можно более центральным по отношению к многограннику, которое принимает минимальное значение. Априори мы ожидаем, что минимизирующая грань должна быть высокой размерности по разным причинам, включая...
В графическом TSP вы получаете невзвешенный неориентированный графггGи цель состоит в том, чтобы найти кратчайший тур в который посещает каждую вершину хотя бы один раз . Обратите внимание , что это не так же , как найти гамильтонов цикл в . Мои вопросы:ггGггG Какова сложность Graphic TSP на...