Question
This problem is one of the last candidates for the NP-intermediate class, meaning it would be in NP yet neither solvable in polynomial time nor NP-complete. For 10 points each:
[10h] Identify this problem, solved in quasipolynomial time in 2015 by Laszlo Babai, which asks whether two given objects are secretly the same.
ANSWER: graph isomorphism problem [prompt on subgraph isomorphism problem; prompt on non-abelian hidden subgroup problem]
[10e] The complement of the graph isomorphism problem is in the Arthur–Merlin class, meaning a system of an“interactive” one of these things can verify it efficiently. To demonstrate the truth of a mathematical statement, one usually provides one of these constructs.
ANSWER: proof [accept interactive proof]
[10m] Graph isomorphism is in the class NP, which stands for problems that can be decided in polynomial time by a Turing machine with this property. Rabin and Scott showed finite automata with this property were equally powerful as a more restricted kind.
ANSWER: nondeterminism [accept nondeterministic; accept nondeterministic polynomial time; prompt on NFA]
<Science - Other Science>
Summary
| 2024 Booster Shot (Waterloo) | 02/23/2024 | Y | 1 | 10.00 | 100% | 0% | 0% |
Data
| Toronto Sprout | Toronto cDNA | 0 | 10 | 0 | 10 |