Проблемы, о которых известно, что они открыты в литературе, и любые проблемы, которые, после их постановки, решаются сообществом.
Википедия перечислены только две проблемы под «нерешенных проблем в области информатики» : P = NP? Существование односторонних функций Какие еще основные проблемы следует добавить в этот список? Правила: Только одна проблема в ответе Предоставьте краткое описание и любые соответствующие ссылки...
Перестановка двух строк формируется путем встраивания символов в новую строку, сохраняя символы каждой строки в порядке. Например, MISSISSIPPIэто перетасовка MISIPPи SSISI. Позвольте мне назвать строковый квадрат, если это тасование двух одинаковых строк. Например, ABCABDCDквадратный, потому что...
фон Несколько лет назад, когда я был студентом, нам дали домашнее задание по амортизированному анализу. Я не смог решить одну из проблем. Я спрашивал об этом в теории , но удовлетворительного результата не было. Я помню курс, на котором Т.А. настаивал на том, что он не смог доказать, и сказал, что...
После изучения детерминированных конечных автоматов (DFA) в старшекурснике, я почувствовал, что они очень хорошо поняты. Мой вопрос: есть ли что-то, чего мы до сих пор не понимаем в них. Я имею в виду не обобщения ДФА, а исходные немодифицированные ДФА, которые мы изучаем в старшекурсниках. Это...
В теме Основные нерешенные проблемы теоретической информатики? Иддо Цамерет сделал следующий превосходный комментарий: Я думаю, что мы должны различать основные открытые проблемы, которые рассматриваются как фундаментальные проблемы, такие как P≠NPP≠NP P\neq NP , и основные открытые проблемы,...
Рассмотрим непересекающихся семейств подмножеств {1,2,…, n}, F 1 , F 2 , … F t .TttF1, F2, … FTF1,F2,…Ft{\cal F}_1,{\cal F_2},\dots {\cal F_t} Предположим, что (*) Для каждого , и каждый R ∈ F я и Т ∈ F к , существует S ∈ F J , который содержит R ∩ T .я < J < Ki<j<ki \lt j \lt kR ∈...
Обновление : теперь известен набор препятствий (то есть «барьер» NxM между размерами окрашиваемой и неокрашиваемой сетки) для всех четырехцветных цветов без монохроматического прямоугольника . Кто-нибудь испытывает желание попробовать 5 цветов? ;) Следующий вопрос возникает из теории Рамсея ....
Эта проблема вдохновлена этим вопросом МО , который мне показался очень интересным. Какая самая старая открытая проблема в TCS? Очевидно, что этот вопрос нуждается в уточнении. Во-первых, что такое TCS? Я думаю, что существование нечетных совершенных чисел не TCS. Я бы сказал, что десятой проблемой...
Недавно Гил Калай и Дик Липтон написали хорошую статью на интересную гипотезу, предложенную Питером Сарнаком, экспертом по теории чисел и гипотезе Римана. Гипотеза. Пусть - функция Мёбиуса . Предположим, что является функцией с входом в виде двоичного представления , тогда f : N → { - 1 , 1 }µ ( k...
Задача состоит в том, чтобы вычислить многочлен . Предположим, что все коэффициенты вписываются в машинное слово, т. Е. Ими можно манипулировать в единицу времени.( а1х + б1) × ⋯ × ( аNх + бN)(a1Икс+б1)×⋯×(aNИкс+бN)(a_1 x + b_1) \times \cdots \times (a_n x + b_n) Вы можете сделать раз, применяя БПФ...
В духе некоторых общих дискуссий, подобных этой , я открываю эту ветку с намерением собрать мнения о том, какие открытые проблемы и актуальные темы в исследованиях по языкам программирования . Я надеюсь, что обсуждение может даже привести к поверхностному мнению относительно будущего исследований в...
Я хотел бы спросить о частном случае вопроса « Решение, вычисляет ли данная схема NC 0 перестановку » QiCheng, который остался без ответа. Булева схема называется цепью NC 0 k , если синтаксически каждый выходной вентиль зависит не более чем от k входных вентилей. (Мы говорим, что выходной вентиль...
Является ли следующая проблема NP-трудной? Учитывая конфигурацию доски для n×nn×nn\times n международных шашек , найдите один законный ход. Соответствующая задача для американских шашек (или английских шашек) тривиально разрешима за полиномиальное время. Есть три основных различия между этими двумя...
Является ли детерминированный алгоритм за полиномиальное время известным для следующей задачи: Ввод: натуральное число (в двоичной кодировке)Nnn Выход: простое число .р > нp>np > n (Согласно списку открытых проблем Леонарда Адлемана, проблема была открыта в 1995 году.)...
Знаковый ранг матрицы A с элементами + 1, -1 является наименьшим рангом (по реалам) матрицы B, которая имеет такой же шаблон знака, что и A (то есть для всех i , к ). Это понятие важно в сложности общения и теории обучения.Aя жВя ж> 0AяJВяJ>0A_{ij}B_{ij}>0я , джя,Ji,j Мой вопрос: существуют...
При постоянная , можно определить в линейное время, учитывая входной граф G , является ли его древесной шириной есть ≤ K . Однако, когда оба k и G даны в качестве входных данных, проблема NP-трудна. ( Источник ).k ∈ Nk∈Nk \in \mathbb{N}гGG≤ k≤k\leq kКkkгGG Однако, когда входной граф является...
В 1999 году Петра Шурман и Герхард Дж. Вёгингер опубликовали статью «Алгоритмы аппроксимации полиномиального времени для машинного планирования: десять открытых задач» . С тех пор, насколько мне известно, обзоры, которые касались бы одного и того же списка проблем, не появлялись. Таким образом,...
Предположим, нам дано несколько непересекающихся простых многоугольников на плоскости и две точки и t вне каждого многоугольника. Задача евклидова кратчайшего пути состоит в том, чтобы вычислить евклидов кратчайший путь от s до t , который не пересекает внутреннюю часть любого многоугольника. Для...
Помимо (детерминированной) сложности связи отношения , другой основной мерой для объема необходимой связи является номер раздела протокола . Связь между этими двумя показателями известна до постоянного фактора. Монография Кушилевица и Нисана (1997) даетRc c ( R )сс(р)cc(R)ррR p p ( R )пп(р)pp(R) c...
В статье «Сборник задач, завершенных для P» Гринлоу, Гувера и Руццо (PS) (PDF) , есть список проблем в P, которые, как известно, не находятся в NC и также не известны как P-полные. , (Этот список включает все открытые проблемы в превосходном обзоре Карпа и Рамачандрана .) Список открытых проблем...