Описание тега np
NP ("nondeterministic polynomial") is a complexity class of decision problems that can be solved by a nondeterministic Turing machine in polynomial time. Equivalently, it is the set of decision problems for which an answer can be verified in polynomial time by a deterministic Turing machine.
1
ответ
Минимизация цветов: вариация алгоритма ранца?
Работая над проектом, я столкнулся с этой проблемой, которую я перефразирую здесь в терминах, выходящих за пределы реальной области проблемы (я полагаю, я мог бы поговорить о калибрах фейерверков и форм, но это усложнит понимание). Я ищу (возможно, …
20 апр '12 в 10:52
1
ответ
Этот алгоритм грубой силы NP-сложный?
Вот алгоритм перебора, который мы используем в системе управления проектами для извлечения ключевых слов из рефератов. Какова временная сложность этого алгоритма перебора? Это NP-жесткий, NP-полный, в NP или в P? Это алгоритм: public static int sear…
09 окт '14 в 07:43
0
ответов
Случайные числа от 1 до -1 в двумерной решетке
Здравствуйте, я должен сделать задание под названием "2D Grid", если у вас есть сердце этого? первая задача состоит в том, чтобы сделать 2D latticeи вопрос идет: Придумайте способ определения квадратного 2D-списка (или Numpy array) содержащие случай…
27 май '14 в 15:26
1
ответ
Почему производительность одного и того же алгоритма цикла отличается
Прямо сейчас я делаю назначения из cs 231 n, и я хотел вычислить евклидово расстояние между точками: dists[i, j]=0 for k in range(3072): dists[i, j]+=math.pow((X[i,k] - self.X_train[j,k]),2) dists[i, j] = math.sqrt(dists[i,j]) однако этот код очень …
15 авг '18 в 09:39
3
ответа
Решение проблем, которые не могут быть решены даже эффективно?
Как эти проблемы попадают в гобелен из комплектов P, NP, NP-Hard и т. Д.? Я не знаю, существуют ли вообще такие проблемы, но то, что инициировало мой мыслительный процесс, было размышлением о разрешении проблемы коммивояжера: Given a list of cities …
31 мар '14 в 20:02
1
ответ
Проблемы НП могут быть решены в детерминистически-экспоненциальное время?
Любая проблема в NP может быть решена за детерминированное экспоненциальное время, или мы можем сказать, что любой язык в NP может быть решен с помощью алгоритма, работающего за время 2^O(n^k), т. е. NP ⊆ EXP неформально говоря, мы просто пробуем ка…
19 ноя '13 в 14:53
1
ответ
Недетерминизм в сравнении с проверяемостью за полиномиальное время
Я читал, что проблема NP может быть проверена за полиномиальное время или, что то же самое, разрешима за полиномиальное время с помощью недетерминированной машины Тьюринга. Почему эти определения эквивалентны?
03 апр '14 в 04:52
1
ответ
Трудно ли NP найти минимальное доминирующее множество, содержащее желаемые вершины?
Для связного неориентированного графа G = (V, E) И желаемый набор вершин D, D is a subset of V (т.е. D \in V) Это NP-hard найти minimum dominating set, содержащий желаемый набор вершин D?
12 май '13 в 04:39
0
ответов
Словари с NumPy - Могу ли я использовать координаты XY в качестве хэша?
У меня есть пустая матрица, представляющая карту координат XY: n = [[0,0],[2,5],[3,1]] Каждая координата связана с рядом других координат, например: [0,0]:[5,2],[3,7] [2,5]:[1,4] [3,1]:[3,7],[5,2],[4,4] У меня вопрос, как я могу хранить эту информац…
29 ноя '14 в 12:21
1
ответ
Измерение сложности NP-комплектного
Например, известно, что проблема решения с заданным покрытием является NP-полной проблемой. Входными данными этой проблемы является юниверс U, семейство S подмножеств U и целое число k (). Одна вещь, с которой меня смущает то, что если мы допустим k…
06 янв '14 в 07:33
1
ответ
Связь между NP и Decision Pro
Государственный T/F. Если кто-то докажет P = NP, то это будет означать, что любая проблема решения может быть решена за полиномиальное время. Я думаю, что это неверно. Я прав?
13 ноя '16 в 08:50
1
ответ
Использование гигантской хэш-таблицы для решения судоку за полиномиальное время
Скажем, вы должны были создать хеш-таблицу, которая отображает каждое возможное действительное судоку 9x9 (еще не заполненное) на его решение. (настолько невыполнимая задача, как это было бы) Затем вы должны были создать простую программу, которая п…
03 апр '18 в 00:11
2
ответа
Путешествующий продавец - приблизительное программное обеспечение онлайн?
Кто-нибудь из вас знает решение для создания даже посредственного решения проблемы коммивояжера. У меня есть 3 человека, которые хотели посетить 31 пункт назначения... Я не знаю, как подойти к этому? Спасибо всем - Максим
21 окт '13 в 17:52
1
ответ
Разбиение списков чисел за полиномиальное время на одинаковые произведения
У меня есть список натуральных чисел L=(n1,n2,...,nk) Я хочу разделить этот список на 2 списка L1 и L2 так, чтобы произведение элементов в списках было одинаковым. Таким образом, произведение (L1) списка L1=(l1,...,lx) равно l1*l2*...*lx. Я хочу мин…
11 авг '14 в 11:04
3
ответа
Необходимо ли, чтобы проблемы NP были решением проблем?
Профессор Тим Рафгарден из Стэнфордского университета, преподавая MOOC, сказал, что решения проблем в классе NP должны быть полиномиальными по длине. Но статья в википедии говорит, что проблемы NP - это проблемы решения. Так какого типа проблемы в о…
10 фев '13 в 15:11
0
ответов
Получить все возможные простые пути между двумя узлами (теория графов)
В контексте теории графов я пытаюсь найти все возможные простые пути между двумя узлами. Я записываю сеть, используя матрицу смежности, хранящуюся в кадре данных pandas, таким образом, что сеть [x][y] хранит значение стрелки, которое идет от x до y.…
05 фев '18 в 17:03
1
ответ
Двойные экспоненциальные проблемы?
Существуют ли какие-либо существенные проблемы в компьютерной науке, которые могут быть решены только в двойном экспоненциальном времени? И если они существуют, то к какому классу проблем они относятся?
11 фев '13 в 17:42
1
ответ
Проблема с созданием столбца с использованием np.where, ошибка ArrayType
У меня есть фрейм данных, в котором я пытаюсь создать двоичный столбец 1/0, когда выполняются определенные условия. Код, который я использую, выглядит следующим образом: sd_threshold = 5 df1["signal"] = np.where(np.logical_and(df1["high"] >= df1[…
07 авг '18 в 16:59
1
ответ
Неперекрывающиеся невыпуклые многоугольники
Предположим, что на плоскости набор из n случайно распределенных невыпуклых многоугольников P={Pi}, n = |P|, некоторые из них перекрываются (примерно 50% перекрывают друг друга). 1] Переместите полигоны так, чтобы не происходило перекрытие. 2] Допус…
05 дек '15 в 11:32
1
ответ
Найти максимальное вершинно-непересекающееся покрытие пути
Предположим, у меня есть ориентированный граф с весами на каждом узле. Вес пути между любыми двумя узлами определяется следующим образом: сумма всех узлов в пути и умножается на количество узлов в этом пути. Мы хотим найти покрытие вершин, не связан…
18 ноя '16 в 05:22