News for hackers. Stuff that matters.
Re:NP-Complete isn't (always) Hard by yarg on Tuesday February 21, 2023 @03:47PM (#34886976)
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.

Re:NP-Complete isn't (always) Hard by JohnKemeny on Thursday February 23, 2023 @05:12PM (#34917332)
SAT 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...

Re:NP-Complete isn't (always) Hard by yarg on Friday February 24, 2023 @03:04PM (#34929362)
It'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.