np

0зной

1ответ

Заполнение прямолинейного многоугольника (с отверстиями) с прямоугольниками

Я прочитал, что это проблема NP. Но мне не нужно наименьшее количество прямоугольников. Просто «более или менее» хороший алгоритм. Итак, проблема. У меня есть бинарная матрица пикселей, похожее на это

algorithm graphics computational-geometry graph-algorithm np 2014-06-17

---

1зной

1ответ

Теорема Кука (на английском языке)

Я прочитал книгу Компьютеры и трудоемкость - руководство по теории NP-полноты от Garey and Johnson для курса моих алгоритмов; однако, после рассмотрения материала через год, я понял, что я никогда не

complexity-theory np-complete np satisfiability 2014-10-02

---

0зной

1ответ

Является ли этот алгоритм грубой силы NP-hard?

Вот алгоритм грубой силы, который мы используем в системе управления проектами для извлечения ключевых слов из тезисов. Какова временная сложность алгоритма перебора? Является ли он NP-твердым, NP-пол

java string algorithm time-complexity np 2014-10-09

---

0зной

1ответ

Уменьшение самостоятельного набора клики?

Покажите, что с учетом графа G и числа k можно каким-то образом преобразовать его в график H такой, что G имеет независимый набор размеров размером не менее k тогда и только тогда, когда H имеет клику

graph np 2014-10-12

---

0зной

1ответ

Является ли Computationally-hard таким же, как NP-hard?

Я хочу знать, есть ли разница между NP-трудными проблемами и сложными вычислительными проблемами или эти два термина используются для одного и того же? Я попытался найти решение, но не могу получить р

computation-theory np computation 2014-10-13

---

1зной

1ответ

Все ли языки принадлежат либо P, либо NP?

Почему я читаю книгу «Теория вычислений Майкла Сипсера», у меня есть небольшой вопрос: принадлежит ли каждый язык к P или NP?

complexity-theory turing-machines np 2014-08-27

---

0зной

2ответ

Вариация упаковки бинов - с классами бинов и объектов и взаимными ограничениями

Я работаю над проблемой, которая является разновидностью бин-упаковки, но немного более общей формой с дополнительными ограничениями. Определение проблемы таково: У нас есть объекты разного размера, к

algorithm optimization np bin-packing 2014-10-30

---

2зной

1ответ

Полиномиальное приближение времени на рюкзак

knapsack problem можно решить в O(n²V), где V = max(v[i], i = 1,..,n) обозначает максимальное значение любого элемента. Если мы «сменим единицы» параметром округления θ = ε/n * V и рассмотрим измененн

algorithm complexity-theory knapsack-problem np 2014-09-15

---