3-SAT problemini Clique problemine indirgeyiniz? 3-SAT problemini polinomsal zamanda Clique problemine indirgeyelim. Aybüke BABADAĞ’ın çözümü için tıklayınız Özyineleme (Recursion) teoremi nedir? NP, NP-Complete, NP-Hard nedir?
mustafa diyor ki: Buradaki nüans eğer klik’i çözebilecek P kategorisinde bu algoritma bulursam o zaman bu algoritma sat’ı da çözmüş olur. Bu durumda indirgenebilen bütün problemler P’de çözülmüş olur. 9 Haziran 2017 - 01:16’ te Cevapla
Buna cevap alamadım
Buradaki nüans eğer klik’i çözebilecek P kategorisinde bu algoritma bulursam o zaman bu algoritma sat’ı da çözmüş olur. Bu durumda indirgenebilen bütün problemler P’de çözülmüş olur.