Описание тега p-np
Used for questions about the P versus NP problem.
7
ответов
Объясните доказательство Vinay Deolalikar, что P!= NP
Недавно в HP Labs была опубликована статья Vinay Deolalikar, в которой утверждается, что она доказала, что P! = NP. Может ли кто-нибудь объяснить, как это доказательство работает для нас менее склонных к математике людей?
09 авг '10 в 02:22
1
ответ
Уменьшение от A до B: верно или неверно
Есть два утверждения: если задача решения A сводится за полиномиальное время к решению проблемы B (т.е. A≤ pB), и B является NP-полным, тогда A должно быть NP-полным. А также: Если задача решения B сводится за полиномиальное время к решению проблемы…
04 дек '15 в 01:52
1
ответ
P равно NP, описание легко
В официальной ссылке проблемы P=NP на странице ниже: P=NP Проблема Официальное описание упоминается проблема организации жилья для группы из четырехсот студентов университета, где вместимость общежития составляет не более 100, а также декан предост…
12 авг '17 в 13:50
6
ответов
NP-сложные проблемы, которые не являются NP-полными, сложнее?
Насколько я понимаю, все NP-полные проблемы являются NP-сложными, но известно, что некоторые NP-сложные проблемы не являются NP-полными, а NP-сложные проблемы, по крайней мере, такие же сложные, как NP-полные. Значит ли это, что NP-сложные задачи, к…
28 сен '10 в 05:26
2
ответа
Может ли сортировка быть P, NP и NP-Complete?
Я очень смущен, и это моя мысль после некоторого прочтения: P находится в NP, а NP находится в NP-Complete. Следовательно, все P могут быть в NP и NP-Complete? Означает ли это, что существуют алгоритмы сортировки, которые могут быть NP и NP-Complete…
12 дек '12 в 10:18
1
ответ
Я нашел в Интернете алгоритм полиномиального времени для раскраски графа, возможно, доказывающий P=NP
Я искал алгоритмы раскраски графа и нашел алгоритм, который, как утверждает автор, работает за полиномиальное время. Автор приводит также исходный код программы C++ и демонстрационную программу. Подозрительным является то, что проблема решения, явля…
08 сен '15 в 17:50
7
ответов
Чего не хватает для этого доказательства P!= NP?
Я пытался восстановить пароль. Размышляя об этом, я осознал, что проблема "восстановление пароля" является очень хорошим примером проблемы NP. Если вы знаете пароль, его очень легко проверить за полиномиальное время. НО, если вы не знаете пароль, ва…
12 дек '09 в 08:56
5
ответов
Почему проблемы NP называются именно так (и NP-hard, и NP-complete)?
Действительно... У меня последний тест на выпускной во вторник, и это одна из вещей, которые я просто никогда не мог понять. Я понимаю, что решение проблемы NP может быть проверено за полиномиальное время. Но при чем тут детерминизм?И если бы вы мог…
08 сен '10 в 20:00
4
ответа
"Поиск всего кода в данном двоичном файле эквивалентен проблеме Остановки". В самом деле?
Просто читал высоко голосованный вопрос относительно Эмуляторов и заявления Было доказано, что поиск всего кода в данном двоичном файле эквивалентен проблеме Halting. Действительно торчал на меня. Конечно, это не может быть правдой? Разве это не бол…
14 мар '11 в 13:59
1
ответ
Проектные предложения для класса сложности
Я беру 400-уровневый класс по сложности и решению проблем. Окончательный проект заключается в реализации проблемы, связанной с P и NP. К сожалению, учитель был непростительно расплывчатым в отношении границ проекта. Так что я просто решил спросить з…
25 фев '13 в 20:24
2
ответа
3SAT решается за полиномиальное время?
Я видел несколько ошибок в файлах cnf как для удовлетворительных, так и для неудовлетворительных файлов предложений. Задачи SATLIB Benchmark Чтобы быть более конкретным, я обнаружил, что 1-й файл в папке zip здесь: 20 переменных, 91 предложение - 10…
26 май '15 в 08:36
1
ответ
Определение NP Complete
Я пытаюсь понять формальное определение NP Complete и у меня возникли вопросы. Мне было интересно, если кто-то может предоставить больше понимания. Книга алгоритмов Джона Кляйнберга говорит, что если каждая проблема NP может быть сведена к проблеме …
22 янв '16 в 20:53
2
ответа
Будет ли экспоненциальная нижняя оценка NP-полного языка доказывать, что P не равен NP?
Если бы кто-то смог доказать экспоненциальную нижнюю оценку для NP-полной задачи, это доказало бы, что P ≠ NP?
18 ноя '13 в 08:22
1
ответ
Sharepoint PNP для разработчиков
Я работаю над программированием SharePoint. Недавно я познакомился с темой под названием Sharepoin Pnp . Какова природа sharepoint pnp? Когда его следует использовать? Какая связь между веб-частью и другими частями программирования SharePoint, таким…
27 мар '18 в 10:55
15
ответов
Каким будет гипотетически доказательство P=NP?
Будет ли это алгоритм с полиномиальным временем для конкретной NP-полной задачи или существуют просто абстрактные рассуждения, демонстрирующие решения NP-полных задач? Кажется, что конкретный алгоритм гораздо полезнее. При этом все, что нам нужно сд…
22 май '09 в 22:31
1
ответ
Простые числа в P - как насчет работы до sqrt?
Я учусь о P а также NP,Я читал, что проблема решения, является ли данное число простым, является проблемой в P, что означает, что у него есть алгоритм полиномиального времени, который решает его.Я также читал, что этот факт был доказан в 2002 году п…
16 авг '14 в 16:21
2
ответа
Opencv: устранить ошибку PNP, EPNP и P3P не удалось
Я пытаюсь сравнить точность и трудоемкость каждой возможности SolvePnP: CV_ITERATIVE, CV_EPNP и CV_P3P Я также сравнил свой результат с Matlab EPNP. И это похоже на провал EPNP и P3P: std::vector<cv::Point2f> imgPoints; imgPoints.push_back(cv:…
23 июн '14 в 09:02
1
ответ
Каковы примеры проблем NP, которые сводятся к NP-полному, но не наоборот?
Каковы примеры NP-задач, которые сводятся к NP-полной проблеме, но не наоборот? Когда я читал о NP и NP-complete, я думал, что отображение будет одно-одно, так что глупо классифицировать их. Тем не менее, безусловно, есть проблемы, которые могут быт…
30 мар '16 в 17:16
2
ответа
Как выбрать только 4 набора целых чисел из набора в алгоритме полиномиального времени
Например, все, что связано с этим полиномиальным временем, сбивает меня с толку: я хочу написать программу с алгоритмом полиномиального времени, который просто выберет только 4 целых числа, сумма которых равна 0 из набора. Например: предположим, у м…
02 фев '16 в 12:52
6
ответов
Что такое "P=NP?", И почему это такой знаменитый вопрос?
Вопрос о том, является ли P=NP, возможно, самым известным во всей информатике. Что это значит? И почему это так интересно? Да, и для дополнительной информации, пожалуйста, опубликуйте доказательство истинности или ложности заявления.:)
21 сен '08 в 16:07