Сводимость по Левину

[Mathdream]

Дайте, пожалуйста, ссылку или объясните коротко.

[bot]

Поищите теорему Левина-Кука или дождитесь, когда сюда заглянет профессор Снэйп

[PAV]

Перенесено из корня в "Помогите..."

[Mathdream]

Теорема Левина-Кука: Проблема выполнимости булевых формул в конъюнктивной нормальной форме NP-полна. Это не то, что нужно. Нужна сводимость, а желательно две из трех: по Левину и по Тьюрингу. По Карпу все просто.