ON THE COMPLEXITY OF THE BANDPASS PROBLEM
Küçük Resim Yok
Tarih
2023
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Inst Applied Mathematics
Erişim Hakkı
info:eu-repo/semantics/closedAccess
Özet
In this paper, we prove that the Bandpass Problem is NP-hard by restriction from the Bandpass Problem to the Satisfiability Problem. Furthermore, we define the 1-Bandpass De-cision Problem, and show that there is a one-to-one correspondence between the k-Satisfiability Decision Problem and the 1-Bandpass Decision Problem.
Açıklama
Anahtar Kelimeler
Bandpass Problem, satisfiability problem, complexity, restriction, NP-hard, NP complete
Kaynak
Twms Journal of Pure and Applied Mathematics
WoS Q Değeri
Q1
Scopus Q Değeri
Cilt
14
Sayı
1
