NP-Completeness & TSP Flashcards
1
Q
What is an NP-complete problem?
A
A problem for which no known polynomial-time algorithm exists, but verifying a solution is polynomial-time.
2
Q
What is the Travelling Salesman Problem (TSP)?
A
Given a set of cities and distances, find the shortest route visiting all cities exactly once and returning to the start.
3
Q
A
4
Q
What does P vs NP mean?
A
P = Problems that can be solved in polynomial time.
NP = Problems where solutions can be verified in polynomial time.
It is unknown if P = NP.
