Существует множество применений реального анализа в теоретической информатике, охватывающих тестирование свойств, сложность коммуникации, обучение PAC и многие другие области исследований. Тем не менее, я не могу думать о каком-либо результате в TCS, который опирается на комплексный анализ (за...
В своем ответе на этот вопрос , Стефан Хименес указал мне на алгоритм нормализации полиномиальное время для доказательств в линейной логике. В доказательстве в статье Жирара используются сети доказательств, которые являются аспектом линейной логики, о которой я на самом деле не очень много знаю. Я...
Я наткнулся на противоречивое разногласие между Агдой и Коком, которое, очевидно, не связано с наиболее известными различиями между их теориями типов (например, (im) предсказуемость, индукция-рекурсия и т. Д.). В частности, Агда принимает следующее определение: data Ty : Set0 -> Set0 where c1 :...
Существует репутация, что в информатике у нас нет научно-популярных книг. Конечно, это не совсем так! (В том же духе из списка « Какие книги должен читать каждый?» , « Какие газеты должен читать каждый?» , « Какие видео должен смотреть каждый?», Созданный по мотивам « Любимой популярной...
Я знаю, что неразрешимо определить, может ли набор плиток укладывать плитку в результате того, что Бергер использовал плитки Ванга . Мой вопрос состоит в том, известно ли также, что неразрешимо определить, может ли один данный фрагмент мозаики составить плоскость - моноэдральный фрагмент . Если это...
Я предполагаю, что я прочитал слишком много амбициозных статей CoRR . Проблема в том, что эти документы не рецензируются, но часто звучат интересно и проходят базовые проверки правдоподобия. Или, может быть, нет, и мне просто нужно улучшить проверку правдоподобия. Вот недавний образец таких работ:...
Я пытаюсь понять связь между изоморфизмом графов и проблемой скрытой подгруппы. Есть хорошая ссылка для
Гипотеза Субхаша Хота об уникальных играх - одно из активных направлений в теории сложности. Какие доказательства у нас есть для этого? Какие доказательства у нас есть против этого?...
Если у меня есть набор линейных ограничений, в которых каждое ограничение имеет не более (скажем) 4 переменных (все неотрицательные и с коэффициентами {0,1}, за исключением одной переменной, которая может иметь коэффициент -1), что известно о решении Космос? Меня меньше беспокоит эффективное...
(Я отправил этот вопрос в MathOverflow две недели назад, но пока без точного ответа) У меня есть вопрос о мерах ширины графа неориентированных простых графов. Хорошо известно, что cographs (графы, которые могут быть построены операциями дизъюнктного объединения и дополнения, начиная с изолированных...
Сообщение обновлено 31 августа : ниже оригинального вопроса я добавил резюме текущих ответов. Спасибо за все интересные ответы! Конечно, каждый может продолжать публиковать любые новые результаты. Для каких семейств графов существует алгоритм полиномиального времени для вычисления хроматического...
Дано это даг. Вы хотите пометить каждый узел тем, сколько узлов доступно из него. - тривиальная верхняя граница; является нижней границей (я думаю). Есть ли лучший алгоритм? Есть ли основания полагать, что нижняя граница может быть улучшена (связана: что именно известно о нижних границах для...
Этот вопрос связан с ответом, который я разместил в ответ на другой вопрос. Задача с 3 разделами представляет собой следующую проблему: Экземпляр : положительные целые числа a 1 ,…, a n , где n = 3m, а сумма n целых чисел равна mB, так что каждый a i удовлетворяет B / 4 <a i <B / 2. Вопрос :...
Ширина дерева показывает, насколько близок график к дереву. NP-трудно вычислить ширину дерева. Наиболее известный алгоритм приближения достигает O ( войдите n----√)O(logn)O(\sqrt{{\log}n}) фактор. Теорема Курселя гласит, что любое свойство графов, определяемых в монадической логике второго порядка...
Что известно о сложности поиска минимальных схем, которые вычисляют SAT до длины ? nnn Более формально: какова сложность функции, которая, учитывая качестве входных данных, выводит минимальную схему C такую, что для любой формулы φ с | φ | ≤ n , C ( φ ) = S A T ( φ )...
В опросе Д. Бера, Ф. Грина и С. Гомера «Квантовые схемы малой глубины» (стр. 36 ACM SIGACT News, июнь 2007 г., том 38, № 2) я прочитал следующее предложение: Классическая версия (в которой вентили и имеют самое большее постоянное разветвление), очевидно, слабее, чем...
Первым шагом алгоритма тестирования простоты AKS является проверка, является ли входное число идеальной степенью. Похоже, что это хорошо известный факт в теории чисел, поскольку в статье это не объясняется подробно. Может кто-нибудь сказать мне, как сделать это за полиномиальное время?...
Вероятно, наиболее распространенным применением линейных типов в PL является использование их для предоставления языков, которые управляют псевдонимами (т. Е. Линейное значение имеет единственный указатель на него, более или менее). Но есть небольшое несоответствие между этим использованием и...
Для A⊂[n]A⊂[n]A\subset [n] обозначим через aiaia_i в ithithi^{th} наименьший элемент AAA . Для двух kkk -элементных множеств A,B⊂[n]A,B⊂[n]A,B\subset [n] мы говорим, что A≤BA≤ВA\le B если ai≤biai≤bia_i\le b_i для каждого iii . kkk -равномерной Гиперграф H⊂[n]H⊂[n]{\mathcal H}\subset [n] ,...
Где я могу найти графики, относящиеся к реальным проблемам? Я знаю два репозитория: Коллекция разреженных матриц Университета Флориды Bodlaender в TreewidthLib