|
Mathdream |
Сводимость по Левину  25.01.2009, 03:06 |
|
18/01/09
27
|
|
Дайте, пожалуйста, ссылку или объясните коротко.
|
|
|
|
 |
|
bot |
26.01.2009, 08:48 |
|
| Заслуженный участник |
 |
21/12/05
5936
Новосибирск
|
|
Поищите теорему Левина-Кука или дождитесь, когда сюда заглянет профессор Снэйп
|
|
|
|
|
|
PAV |
26.01.2009, 13:29 |
|
| Супермодератор |
 |
29/07/05
8248
Москва
|
|
Перенесено из корня в "Помогите..."
|
|
|
|
|
|
Mathdream |
29.01.2009, 18:54 |
|
18/01/09
27
|
|
Теорема Левина-Кука: Проблема выполнимости булевых формул в конъюнктивной нормальной форме NP-полна. Это не то, что нужно. Нужна сводимость, а желательно две из трех: по Левину и по Тьюрингу. По Карпу все просто.
|
|
|
|
|
  |
Страница 1 из 1
|
[ Сообщений: 4 ] |
|
Модераторы: Модераторы Математики, Супермодераторы
