Предположим, у нас есть матрица n на n. Можно ли изменить порядок строк и столбцов так, чтобы мы получили верхнетреугольную матрицу? Этот вопрос мотивирован этой проблемой: положительный топологический порядок Первоначальная проблема решения, по крайней мере, так же сложна, как эта, поэтому...
DFA имеет синхронизирующее слово, если есть строка, которая отправляет любое состояние DFA в одно состояние. В «Гипотезе Черни для апериодических автоматов» А. Н. Трахтмана («Дискретная математика и теоретическая информатика», том 9: 2, 2007, с. 3-10) он писал: В 1964 году Черни предположил, что...
Какие основные открытые проблемы вычислительной сложности возникают из-за языков программирования, особенно из анализа и компиляции программ? Я ищу проблемы по линии «временная сложность вывода типа Хиндли-Милнера» или «временная сложность 0CFA» (хотя обе проблемы...
Я читал, что целочисленное линейное программирование разрешимо за полиноминальное время, если число переменных фиксировано, т.е. n ∈ O ( 1 ) . Если число переменных растет логарифмически, т. Е. N ∈ O ( log 2 ( N ) ) для заданного входного значения размера N , проблема все еще разрешима за...
Фон Функции в могут быть изучены PAC в квазиполиномиальном времени с помощью классического алгоритма, который требует случайно выбранных запросов, чтобы изучить схему глубины d [1]. Если нет факторинг-алгоритма , то это оптимально [2]. Конечно, на квантовом компьютере мы знаем, как учитывать,...
Интересно, как найти обхват разреженного неориентированного графа. Под разреженным я подразумеваю . Под оптимальным я подразумеваю минимальную временную сложность.|E|=O(|V|)|E|=O(|V|)|E|=O(|V|) Я думал о некоторой модификации алгоритма Тарьяна для неориентированных графов, но я не нашел хороших...
Меня интересует «ближайшая» (и «самая сложная») проблема к гипотезе Коллатца , которая была успешно решена (на что Эрдос сказал, что «математика еще не созрела для таких задач»). Было доказано, что класс "коллатцовых" проблем неразрешим. Тем не менее, проблемы, которые в некоторой степени похожи,...
Цель : сформулировать гипотезу об отсутствии проективной плоскости порядка 12. В 1989 году, используя компьютерный поиск на Крей, Лэм доказал, что проективной плоскости порядка 10 не существует. Теперь, когда число Бога для кубика Рубика было определено после нескольких недель масштабного поиска...
Рассмотрим такой язык LLL , что: L∈DTIME(O(f(n)))∩DSPACE(O(g(n)))L∈DTIME(O(f(n)))∩DSPACE(O(g(n)))L \in DTIME(O(f(n))) \cap DSPACE(O(g(n))) и так что L∉DTIME(o(f(n)))∪DSPACE(o(g(n)))L∉DTIME(o(f(n)))∪DSPACE(o(g(n)))L \not\in DTIME(o(f(n))) \cup DSPACE(o(g(n))) Другими словами, самая быстрая машина...
В главе 1 книги «Вероятностный метод» Алона и Спенсера упоминается следующая проблема: Учитывая граф , решите, является ли его граничная связность по крайней мере или нет.GGGn/2n/2n/2 Автор упоминает о существовании алгоритма от Matula и улучшает его до...
Известно, что определение того, является ли данное триангулированное 3-многообразие 3-сферой, входит в NP посредством работы Сола Шлеймера в 2004 году: «Распознавание сфер лежит в NP» arXiv: math / 0407047v1 [math.GT] . Я задаюсь вопросом, было ли это установлено, чтобы быть законченным NP за...
Теория компилятора, кажется, довольно проверенная тема. Какие открытые проблемы или текущие исследования происходят в этой
Автор: http://www.cs.umd.edu/~jkatz/complexity/relativization.pdf. Если является PSPACE-полный язык, Р = N P A .AAAпA= NпAPA=NPAP^{A}=NP^{A} Если является детерминированным оракулом полиномиального времени, P B ≠ N P B (при условии, что P ≠ N P ).ВBBпВ≠ NпВPB≠NPBP^{B}\ne NP^{B}п≠ NпP≠NPP\ne NP -...
Какие проблемы со следующими свойствами: 1) они являются ограничением (возможно общеизвестных) проблем, которые являются PSPACE-полными; 2) ограниченные версии находятся в PSPACE, но это открытая проблема, если они завершены PSPACE (или даже если они NP-hard). Четыре примера из "головоломки и С.":...
Я ищу список об известной или неизвестной сложности различных теоретико-алгебраических задач. Например, GCD в открыт,NC1NC1NC^1 факторинг в открыт,PPP вычисление когомологий пучка -hard#P#P\#P , Арора и Барак утверждают, что вариант факторинга является -полным (хотя это не ясно из обсуждения в...
Greibach лихо определил язык , так называемую недетерминированную версию о , таких , что любая КЛЛ является обратной морфической изображение . Существует ли подобное утверждение с DCFL, возможно, с некоторыми ограничениями на допустимые морфизмы?D 2 HЧАСHHD2D2D_2ЧАСHH (См., Например, М. Аутеберт,...
В проектах Polymath большая группа работает над открытой проблемой. Какие проблемы лучше всего работают в этих рамках? Есть ли хорошие кандидаты для участия в проекте по математике в теоретической информатике? Существуют ли какие-либо препятствия, которые делают проекты Polymath менее успешными в...
В сложности связи гипотеза лог-ранга утверждает, что с с ( М) = ( журналr k ( М) )O ( 1 )cc(M)=(logrk(M))O(1)cc(M) = (\log rk(M))^{O(1)} Где - сложность связи а - ранг (в виде матрицы) над реалами.M ( x , y ) r k ( M ) Mс с ( М)cc(M)cc(M)M( х , у)M(x,y)M(x,y)r k ( М)rk(M)rk(M)MMM Однако, когда вы...
Мы знаем, что . Из теоремы Савича и из теоремы пространственной иерархии . Итак, поскольку мы не знаем, , мы не знаем, , или мы знаем, что ? Кто-нибудь пытался доказать, что \ mathcal L ^ 2 \ subseteq \ mathcal P ? Каковы последние результаты или усилия в этом направлении? Я пытался написать опрос...
Я наткнулся на статью, опубликованную в Science, «Memcomputing NP-полных задач за полиномиальное время с использованием полиномиальных ресурсов и коллективных состояний» , в которой содержатся довольно удивительные утверждения. Memcomputing - это новая парадигма вычислений, отличная от Тьюринга, в...