o far we have discussed efficient algorithms for selected problems. In this section we will discuss problems for which no efficient algorithm is known. From now on we will consider • Polynomial time algorithm is “practical”. • Exponential and...See more
worse is “impractical”.
In this part of the course we will: • Introduce theory of NP-completeness • Introduce the famous P = NP open problem • Learn how to prove that a problem is NP-complete
Answer the Question