Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Lecture
Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
This lecture explores examples of NP problems, focusing on graph coloring problems and path optimization. It discusses the complexity of finding solutions, including the distinction between problems in P and NP classes. The instructor presents various algorithms and proofs related to graph coloring, highlighting the challenges of efficient computation. Additionally, the lecture delves into path traversal problems, such as Eulerian and Hamiltonian paths, showcasing the differences in complexity and available algorithms. The classification of decision problems based on computational complexity is also covered, emphasizing the significance of NP-complete problems in various domains.