Більш швидкий доступ, ніж браузер!
8 відносини: NP-повна задача, Satisfiability Modulo Theories, Клас складності NP, Клас складності P, Кон'юнктивна нормальна форма, Проблема трійок Буля-Піфагора, Стівен Кук, Диз'юнктивна нормальна форма.
NP-повна задача
Діаграма Венна відношення між класами складності задач (у випадку вірності гіпотези P ≠ NP). NP-повна задача (NP-complete) — в теорії алгоритмів та теорії складності це задача, що належить до класу NP та всі задачі з класу NP можна звести до неї за поліноміальний час.
Новинка!!: Задача здійсненності бульових формул і NP-повна задача · Побачити більше »
Satisfiability Modulo Theories
У програмуванні, Satisfiability Modulo Theories (SMT) — це задача розв'язності для логічних формул з урахуванням теорій, які лежать в їх основі.
Новинка!!: Задача здійсненності бульових формул і Satisfiability Modulo Theories · Побачити більше »
Клас складності NP
Клас складності NP (Complexity class NP) — клас складності, до якого належать задачі, що можна розв'язати недетермінованими алгоритмами за поліноміальний час; тобто, недетермінованими алгоритмами в яких завжди існує шлях успішного обчислення за поліноміальний час відносно довжини вхідного рядка; очевидно, що \mathcal \subseteq \mathcal.
Новинка!!: Задача здійсненності бульових формул і Клас складності NP · Побачити більше »
Клас складності P
Клас складності P (Complexity class P) — клас задач, що можна розв'язати алгоритмами з поліноміальним часом.
Новинка!!: Задача здійсненності бульових формул і Клас складності P · Побачити більше »
Кон'юнктивна нормальна форма
Кон'юнкти́вна норма́льна фо́рма (КНФ) в булевій логіці - нормальна форма в якій булева формула має вид кон'юнкції декількох диз'юнктів (де диз'юнктами називаються диз'юнкції декількох пропозиційних символів або їх заперечень).
Новинка!!: Задача здійсненності бульових формул і Кон'юнктивна нормальна форма · Побачити більше »
Проблема трійок Буля-Піфагора
Ердешем Проблема трійок Буля-Піфагора запитує, чи можна поділити множину натуральних чисел \ на дві частини так, щоб кожна частина не мала жодної піфагорової трійки.
Новинка!!: Задача здійсненності бульових формул і Проблема трійок Буля-Піфагора · Побачити більше »
Стівен Кук
Стівен Артур Кук (Stephen Arthur Cook 14 грудня 1939) — канадський та американський математик та науковець у галузі теоретичної інформатики, лауреат премії Тюрінга.
Новинка!!: Задача здійсненності бульових формул і Стівен Кук · Побачити більше »
Диз'юнктивна нормальна форма
Диз'юнкти́вна норма́льна фо́рма (ДНФ) в булевій логіці — нормальна форма в якій булева формула має вид диз'юнкції декількох кон'юнктів (де кон'юнктами називаються кон'юнкції декількох пропозиційних символів або їх заперечень).
Новинка!!: Задача здійсненності бульових формул і Диз'юнктивна нормальна форма · Побачити більше »
Перенаправлення тут:
SAT проблема, Задача здійснимості булевих формул, Задача здійснимості бульових формул.
