Checking for optimal solutions in some $NP$-complete problems

Henri Orland, Michel Bauer

For some weighted $NP$-complete problems, checking whether a proposed solution is optimal is a non-trivial task. Such is the case for the celebrated traveling salesman problem, or…