Maybe it sounds simple to computer scientists, I just want to backup some logical deduction of myself in NP-completeness proofs in case I will deal with such proofs in the future. In NP-completeness proof, we always want to find a polynomial-time reduction (transformation) from problem A to problem B, denoted as: We say that there …
Continue reading “Logical deduction in NP-completeness proof”