This man’s namesake law states that “debugging is twice as hard as writing the code in the first place.” For 10 points each:
[10h] Give this man who names an algorithm with logarithmic worst case time complexity for counting the number of set bits in a binary number. With Lin, he names a heuristic that extends the k-opt algorithm.
ANSWER: Brian Kernighan [accept Lin–Kernighan heuristic]
[10m] The aforementioned Lin–Kernighan heuristic and k-opt algorithm are methods for solving this problem. This problem seeks to locate the shortest Hamiltonian cycle on a weighted graph.
ANSWER: traveling salesman problem [or TSP; or traveling salesperson problem]
[10e] The traveling salesman problem is classified under a complexity class named for these two letters and “hard.” Whether another complexity class of this two-letter name equals P is the subject of a Millennium Prize Problem.
ANSWER: NP-hard [or nondeterministic polynomial; accept P versus NP]
<DN, Other Science - Computer Science>