Ask HN: How is the job search coming along for people who got laid off?

Re:Ask HN: How is the job search coming along for people who... by dllthomas on Tuesday December 06, 2022 @04:38PM (#33887426)

You can offer. Nothing about it being NP should prevent your implementing an exact solution, though. It'll be slow as balls on (at least) some inputs, and you should surface that, but maybe they only need something that works for N<5 or something.

That's different than it being undecidable, in which case you have to insist on providing something other than an exact algorithm that handles every input.

[ Parent | on HN ]

Re:Ask HN: How is the job search coming along for people who... by nephanth on Friday December 09, 2022 @01:06PM (#33924466)

For the short story. A few years ago I was sitting a CS exam that was 3 hours of coding and then a defense where you explained what you have done on the board.

You had to compute a graph from a set of points (i think it was knn, not sure) and do stuff on it. At some point of the defense, this happened

Me: I skipped this question.

Examinator: why?

Me: If I compute it using the graph structure, it reduces to max-clique, which is np-complete. I looked for a solution using the point dara but didn't find it

Examinator: can you write an algorithm for max-clique on the board?

Me: here. This is exponential time

Examinator: it's worst case exponential time. But in this case it would have worked, you just had to try it

Me: urgh

Now I've learned my lesson: np-complete doesn't mean impossible

[ Parent | on HN ]