Графы без X - это графы, которые не содержат графов из X в качестве индуцированного подграфа. Отверстие представляет собой цикл, по крайней мере 4 -х вершин. Нечетное отверстие представляет собой отверстие с нечетным числом вершин. Antihole является дополнением дырки. Графики (нечетные дыры,...
Этот вопрос о странице 125 книги «Клеточные автоматы в гиперболических пространствах: Том 2» Мориса Маргенстерна, Publisher Archives современники, 2008. http://books.google.com/books?id=eEgvfic3A4kC&pg=PA125 По мнению автора, вопрос P = NP некорректен, поскольку в гиперболическом сеттинге P =...
Рассмотрим следующий процесс: Есть корзин, расположенных сверху вниз. Первоначально, каждая корзина содержит один шар. На каждом шагу мыNNn выбрать мяч равномерно наугад иббb переместите все шары из корзины, содержащей в корзину под ней. Если это уже была самая низкая корзина, мы удаляем шары из...
Предположим, у вас есть два произвольно влиятельных участника, которые не доверяют друг другу. У них есть доступ к обязательству по битам (например, запечатанные конверты, содержащие данные, которые один игрок может передать другому, но которые нельзя открыть, пока первый игрок не даст второму...
( UPDATE : лучше формируются вопрос ставятся здесь в качестве комментариев к общепринятом ответу ниже , показывает , что этот вопрос не является четко определенным) Классическое доказательство невозможности проблемы остановки зависит от демонстрации противоречия при попытке применить алгоритм...
Функция f:{0,1}∗→{0,1}∗f:{0,1}∗→{0,1}∗f \colon \{0, 1\}^* \to \{0, 1\}^* является односторонней, если fff может быть вычислена с помощью алгоритма полиномиального времени, но для каждого рандомизированного алгоритма полиномиального времени AAA,...
Учитывая набор S из nxn матриц перестановок (который является лишь малой долей из n! Возможных матриц перестановок), как мы можем найти подмножества T минимального размера в S, чтобы при добавлении матриц T было по крайней мере 1 в каждой позиции? Меня интересует эта проблема, где S - небольшая...
Это вопрос в духе этого, где я ответил, что важно отслеживать, что вы сделали, почему вы это сделали, а что нет. Я лично использую ноутбуки для этой цели, но у нее есть несколько недостатков: во-первых, мне нужно много места для хранения, во-вторых, когда я путешествую, я не могу получить доступ к...
Нам дано семейство из подмножеств {1, ..., n}. Можно ли найти нетривиальную нижнюю оценку сложности решения, является ли семейством Спернера? Тривиальная нижняя граница - и я сильно подозреваю, что она не жесткая.FF\mathcal{F}mmmFF\mathcal{F}O(nm)O(nm)O(n m) Напомним, что множество является...
Для заданных точек в R d и расстояния l найти наибольшее подмножество этих точек, такое, что евклидово расстояние ни одной из них не превышает l .p1,…,pnp1,…,pnp_1,\ldots,p_nRdRd\mathbb{R}^{d}llllll В чем сложность этой проблемы? На графике точек, имеющих ребро, когда расстояние между двумя точками...
В недавнем вопросе обсуждался теперь классический алгоритм динамического программирования для TSP, независимо от Беллмана и Хельда-Карпа . Алгоритм повсеместно сообщается работать в O(2nn2)O(2nn2)O(2^n n^2) времени. Однако, как недавно заметил один из моих учеников, это время выполнения может...
Учитывая два дерева AVL и и значение такое что , легко построить новое дерево AVL, содержащее и значения в и за время , где обозначает высоту дерева (до тех пор, пока деревья хранят свою высоту).Т 2 т г ∀ х ∈ T 1 , ∀ у ∈ Т 2 , х < т г < у т т Т 1 Т 2 О ( 1 + | ч ( Т 1 ) - ч ( Т 2 ) | ) ч ( Т...
Обозначим через колмогоровскую сложность строки x . Существуют ли такие строки, что K ( x x ) < K ( x ) . (Здесь x x - это сцепление x с самим собой). Похожий , но другой вопрос был задан здесь , но контрпример дается в ответ на этот вопрос не работает для...
Существует стандартная теория приближений, в которой коэффициент приближения равен supAOPTвирAОпT\sup\frac{A}{OPT} (для задач сMINMяNMINзадачами),AAA- значение, возвращаемое некоторым алгоритмомAAAаOPTОпTOPT- оптимальное значение. И еще одна теории, что издифференциального приближениягде отношение...
Хорошо известно, что случайные формулы -CNF над n переменными с предложениями c n являются неудовлетворительными (т.е. являются противоречиями) с большой вероятностью для достаточно большой постоянной c . Таким образом, случайные формулы k- CNF (для достаточно больших c ) представляют собой...
После небольшой работы с 2-3 пальцами я был впечатлен их скоростью в большинстве операций. Однако одна проблема, с которой я столкнулся, - это большие накладные расходы, связанные с первоначальным созданием большого дерева пальцев. Поскольку построение определяется как последовательность операций...
Мне было интересно, есть ли хорошая библиография попыток исследовать гипотезу Коллатца как формальную грамматику? (или любые другие попытки в сообществе CS иметь дело с этим классом порождающих явлений и их «препятствующими»...
Существует ли какая-либо теория языков программирования, описывающая интерфейсы сторонних функций (FFI) и привязки к нескольким языкам? Я задал некоторые вопросы реализации на стеке потока , который здесь не подходит. Но я хотел бы спросить с точки зрения этого сайта и посмотреть, что я мог бы...
Одна из удивительных вещей в компьютерной науке заключается в том, что физическая реализация в некотором смысле «неактуальна». Люди успешно создали компьютеры из нескольких различных подложек - реле, вакуумных трубок, дискретных транзисторов и т. Д. Вскоре люди могут преуспеть в создании...
Является ли случай строго регулярных графов самым сложным для тестирования ЖКТ? где «самый трудный» используется в некотором смысле «здравый смысл», или, так сказать, «в среднем». Wolfram MathWorld упоминает некоторые «патологически сложные графы». Кто они такие? Мой примерный набор из 25 пар...