Меня интересует «ближайшая» (и «самая сложная») проблема к гипотезе Коллатца , которая была успешно решена (на что Эрдос сказал, что «математика еще не созрела для таких задач»). Было доказано, что класс "коллатцовых" проблем неразрешим. Тем не менее, проблемы, которые в некоторой степени похожи,...
Ответ: не известно. Задаваемые вопросы являются естественными, открытыми и, по-видимому, сложными; сейчас вопрос вики сообщества. обзор Вопрос состоит в том, чтобы разделить языки, принадлежащие к классу сложности PPP - вместе с машинами Тьюринга (TM), которые принимают эти языки, - на два...
Какова наиболее известная сложность запроса алгоритма обучения Голдрайха-Левина? Лекционные заметки из блога Лука Тревисан в , леммы 3, утверждает его как . Это самый известный с точки зрения зависимости от п ? Буду особенно благодарен за ссылку на цитируемый источник!O ( 1 / ϵ4журнал nн...
Я ищу информацию о вычислительной сложности матричного умножения прямоугольных матриц. Википедия утверждает, что сложность умножения на составляет (умножение в школьных учебниках).A∈Rm×nA∈Rm×nA \in \mathbb{R}^{m \times n}B∈Rn×pB∈Rn×pB \in \mathbb{R}^{n \times p}O(mnp)O(mnp)O(mnp) У меня есть...
Мы знаем, что если разрыв между значениями целочисленной программы и ее двойственной («двойственность разрыв») равен нулю, то линейные программные релаксации целочисленной программы и двойственной релаксации, оба допускают интегральные решения (нулевая) интегральность разрыв "). Я хочу знать, верно...
Я начинаю свою докторскую диссертацию этой осенью и планирую работать над теорией сложности для своей диссертации. Я составляю список важных работ, которые должен знать каждый теоретик сложности. Какие документы вы бы предложили человеку, как я? И, пожалуйста, кратко объясните, почему вы считаете...
Мой первый вопрос: известна ли интерактивная характеристика системы доказательств для всех классических классов сложности. Я бы назвал P, NP, PSPACE, EXP, NEXP, EXPSPACE рекурсивными и рекурсивно перечислимыми функциями классическими (среди прочих). В частности, известна ли интерактивная...
Функциональный язык можно рассматривать как категорию, где его объектами являются типы и функции морфизмов между ними. Как классы типов вписываются в эту модель? Я предполагаю, что мы должны рассматривать только те реализации, которые удовлетворяют ограничению, которое имеет большинство классов...
Результат 1: Теорема Линиала-Мансура-Нисана говорит о том, что вес Фурье функций, вычисленных по схемам сосредоточен на подмножествах малого размера с высокой вероятностью.AC0AC0\mathsf{AC}^0 Результат 2: вес Фурье у сконцентрирован на коэффициенте степени n .PARITYPARITY\mathsf{PARITY}nnn Вопрос:...
Меня интересуют графики по вершинам, которые можно получить с помощью следующего процесса.nnn Начнем с произвольного графа на вершинах. Пометьте все вершины в как неиспользуемые .GGGGk≤nk≤nk\le nGGG Производят новый граф , добавив новую вершину , который соединен с одним или более неиспользованных...
GI и проблема узлов являются проблемой определения структурной эквивалентности математических объектов. Есть ли какие-либо результаты установления связей между ними? Хорошие связи проблемы узлов со статистической физикой были изучены с помощью полиномов узлов , есть ли похожие результаты для ?G...
Я вспоминаю, как видел исследование или статью, где недавно утверждалось, что большая часть ускорения, наблюдаемого в компьютерных программах за последние несколько десятилетий, происходит от более совершенных алгоритмов, а не от более быстрого аппаратного обеспечения. Кто-нибудь знает исследование...
Я читаю " Объединение регулярных языков и сложность описания " Галины Йирасковой, 2009 г., о сложности состояний, возникающей в результате объединения двух регулярных языков (Галина Жираскова), но я не могу понять, каковы будут практические последствия сложности состояний , Первая тривиальная...
Какой класс сложности связан с исчерпывающими алгоритмами поиска? (если есть) Это NP или PSPACE? Существуют ли ограниченные модели вычислений, охватывающие класс алгоритмов исчерпывающего поиска, аналогичных моделям для жадного и динамического...
Рассмотрим мерное пространство , и пусть - линейное ограничение вида , где , и k \ in \ mathbb {R} .nnn{0,1}n{0,1}n\{0,1\}^nccca1Икс1+ а2Икс2+ а3Икс3+ . , , + а n - 1Иксn - 1+ аNИксN≥ ka1x1+a2x2+a3x3+ ... +an−1xn−1+anxn≥ka_1x_1 + a_2x_2 + a_3x_3 +\ ...\ + a_{n-1}x_{n-1} + a_nx_n \geq kaя∈ Rai∈Ra_i...
В статье « Рандомизированный анализ ранга-двойственности RANKING для сопоставления двухчастных он- лайн , доказывая, что алгоритм RANKING является -конкурентоспособным, авторы показывают, что двойственное возможно в ожидание (см. лемму 3 на стр. 5). Мой вопрос:( 1 - 1е)(1-1е)\left(1 -...
Популярная игра на праздничных вечеринках в Северной Америке - обмен подарками белых слонов . Вкратце (без учета вариаций) это работает следующим образом: Есть людей и упакованных подарков. Игроки заказаны произвольно. В раунде , игрок либоNNnNNnягоiгоi^{\text{th}}яяi выбирает завернутый подарок и...
Принимая во внимание в качестве входных данных целое число и множество S наборов элементов { 1 , . , , , П } , что является сложность нахождения множество Т элементов { 1 , . , , , n } такой, что T имеет минимальную мощность и T не входит ни в один из множеств S ?nnnSSS{1,...,n}{1,...,n}\{1, ...,...
Будучи студентом, изучающим информатику, я познакомился с теорией игр, но не видел подробностей по этому вопросу. Я искал в Google и просмотрел несколько книг по теории игр, и они предоставили подтверждение ее использования в информатике. Я начал формальное изучение теории игр с точки зрения...
Хорошо известно, что никакой детерминированный двухсторонний протокол не может решить проблему дизъюнктивности (DISJ) на битных входах без отправки n + 1 бит в худшем случае (см., Например, книгу Kushilevitz and Nisan). Для рандомизированных протоколов с ограниченной ошибкой нижняя граница δ n для...