На прошлой неделе я снова читал текст Лесли Лампорта, опубликованный в 1982 году, на конференции, которую он дал о « Решенных проблемах, нерешенных проблемах и проблемах в параллелизме» . Бумага легко читается, но одна из вещей, которая заставила меня задуматься, это следующее утверждение: Можно ли...
Я ищу структуру данных, которая бы поддерживала целочисленную таблицу ttt размера и позволяла бы выполнять следующие операции за время .nnnO(logn)O(logn)O(\log n) increase(a,b)increase(a,b)\text{increase}(a,b) , которое увеличивает .t[a],t[a+1],…,t[b]t[a],t[a+1],…,t[b]t[a],t[a+1],\ldots,t[b]...
Для ориентированного циклического графа, где вес каждого ребра может быть отрицательным, концепция «кратчайшего пути» имеет смысл, только если нет отрицательных циклов, и в этом случае вы можете применить алгоритм Беллмана-Форда. Тем не менее, я заинтересован в поиске кратчайшего пути между двумя...
Что известно о классе языков, распознаваемых конечными автоматами, имеющими одинаковое начальное и принимающее состояние? Это правильное подмножество обычных языков (поскольку каждый такой язык содержит пустую строку), но насколько он слаб? Есть ли простая алгебраическая характеристика? То же самое...
Дана матрица A с рациональными элементами. В чем сложность проверки А диагонализируемой?n × nN×Nn\times nAAAAAA Я подозреваю, что это может быть сделано в P, но я не знаю никаких ссылок. Однако, более интересный вопрос, есть ли лучший класс сложности для решения этой проблемы? Любое руководство /...
Известно, что многие логические проблемы (например, проблемы выполнимости нескольких модальных логик) не разрешимы. Есть также много неразрешимых проблем в теории алгоритмов, например, в комбинаторной оптимизации. Но на практике эвристики и приближенные алгоритмы хорошо работают для практических...
Неформально односторонние функции определены в отношении алгоритмов PTIME. Они вычислимы за полиномиальное время, но не обратимы в полиномиальное время среднего случая. Существование таких функций является важной открытой проблемой в теоретической информатике. Я заинтересован в односторонних...
Пусть - булева функция от n булевых переменных. Пусть g ( x ) = T ϵ ( f ) ( x ) будет ожидаемым значением f ( y ), когда y получается из x путем переключения каждой координаты с вероятностью ϵ / 2 .fffnnng(x)=Tϵ(f)(x)g(x)=Tϵ(f)(x)g(x)=T_\epsilon (f) (x)f(y)f(y)f(y)yyyxxxϵ/2ϵ/2\epsilon/2 Меня...
Вспомните преобразование прохождения продолжения (преобразование CPS), которое переводит в (где фиксировано) и до определяется как На самом деле у нас есть монада продолжения с единицей определенной как и умножение определяемое как β A : = R R A R f : A → B β f : β A → β B βAAAβA:=RRAβA:=RRA\beta A...
В связи с этим вопросом мне пришло в голову задаться вопросом: какова временная сложность одноленточной машины Тьюринга с одной головкой для вычисления длины ее входных данных? Чтобы быть точным, скажем, что алфавит ленты равен , входные данные представляют собой строку в ( 0 + 1 ) ∗, окруженную...
Рассмотрим следующую проблему. Вход: неориентированный граф . Вывод: граф H, который является младшим из G с самой высокой граничной плотностью среди всех миноров G , то есть с самым высоким отношением | E ( H ) | / | V ( H ) | ,G=(V,E)G=(V,E)G=(V,E)HHHGGGGGG|E(H)|/|V(H)||E(H)|/|V(H)||E(H)|/|V(H)|...
Что такое теоретическая информатика? Это обучение кодированию на разных языках и создание приложений на платформах? Или это просто думать о более быстрых и быстрых алгоритмах, чтобы вы могли более эффективно решать задачи с помощью компьютеров? Или это программирование и размышление о новых...
Насколько я понимаю, доказательство того, что P = NP или P ≠ NP, должно быть нерелятивизируемым (как в оракулах теории рекурсии). Практически все доказательства кажутся релятивизируемыми. Какие хорошие примеры , не являющиеся Релятивизуемых доказательств, из тех , что Р = NP / P ≠ NP доказательству...
Некоторое время назад я опубликовал справочный запрос для задач с графами, где мы хотим найти 2-секционное ребро, в котором оба набора удовлетворяют свойству, не связанному с их количеством элементов. Я пытался доказать, что следующая проблема NP-трудна: Для турнира существует ли множество дуг...
В Bundeswettberweb Infomatik 2010/2011 возникла интересная проблема: Для фиксированного найдите минимальное k и отображение φ : { ( i , j ) | i ≤ j ≤ n } → { 1 , … , k } , так что не существует тройки ( i , j ) , ( i + l , j ) , ( i + l , j + l ) с φ ( iNNnККkφ : { ( i , j ) | i ≤ j ≤ n } → { 1 , …...
Предположим, что P NP.≠≠\ne Теорема Ладнера гласит, что существуют промежуточные проблемы NP (проблемы в NP, которые не находятся ни в P, ни в NP-Complete). Я нашел несколько завуалированных ссылок в Интернете, которые предполагают (я думаю), что в NPI существует много «уровней» взаимно сводимых...
Могут ли все последующие одновременно выполняться? LsLsL_s содержится в для всех натуральных чисел . sLs+1Ls+1L_{s+1}sss L=⋃sLsL=⋃sLsL = \bigcup_s L_s - это язык всех конечных слов над .{0,1}{0,1}\{0,1\} Существует некоторый класс сложности и понятие соответствующего сокращения для такой , что для...
Предположим, что существует граф . Я хочу проверить, можно ли разделить V на два непересекающихся множества V 1 и V 2 , так что подграфы, индуцированные V 1 и V 2, являются графами с единичным интервалом.G=(V,E)G=(V,E)G=(V,E)VVVV1V1V_1V2V2V_2V1V1V_1V2V2V_2 Я знаю о NP-полноте определения...
Предположим, вы встречаетесь с программистами, которые прошли некоторые профессиональные курсы по программированию (или думали сами), но не изучали математику университетского уровня. Чтобы показать им всю прелесть TCS, я хотел бы собрать некоторые хорошие результаты / открытые вопросы, поступающие...
Мы дали направленный ациклический граф с номером , связанным с каждой вершиной ( г : V → N ), и целевым числом Т ∈ N .G=(V,E)G=(V,E)G=(V,E)g:V→Ng:V→Ng:V\to \mathbb{N}T∈NT∈NT\in \mathbb{N} Проблема DAG подмножества суммы (может существовать под другим именем, ссылка будет большой) спрашивает , есть...