3 ms·
I think the complexity of the problem is such that even a lot of lecturers don't really understand it. I remember in one lecture where the dude drew an unweigh
by yarg 4y ago
I think the complexity of the problem is such that even a lot of lecturers don't really understand it.
I remember in one lecture where the dude drew an unweighted graph on the board, claiming it to be in NP.
But he'd already proven it to be planar (by construction), which (and correct me if I'm wrong) simplifies the problem to P.
- JohnKemeny 4y agoSAT is NP-complete even when the variable-clause graph is planar. Vertex cover is NP-complete on planar graphs even if each vertex has at most three neighbors. Travelling Salesman is NP-complete on planar graphs. So is independent set, dominating set, 3-coloring...
- yarg 4y agoIt's not the travelling salesman - as per the description it's an unweighted graph. This reduces the problem from finding the shortest hamiltonian cycle to finding any such cycle.