Question
Problems known to be at least as hard as the hardest problems in this class are known as ‘this class’-hard, whilst problems within it which can simulate every other problem in it are known as ‘this class’-complete. For 10 points each:
[10e] Name this computational complexity class. One of the Millennium problems asks for a proof for either the statement that this class is equal to P or not.
ANSWER: NP [accept nondeterministic polynomial time]
[10m] The Cook-Levin theorem states that this specific NP problem is NP-complete. This problem asks whether for a given Boolean formula, some assignment of truth values makes the formula true.
ANSWER: boolean satisfiability [or SAT; accept 3SAT]
[10h] It is known that P=NP cannot be settled using only relativizing proofs, which are ones that hold relative to all of these abstract devices.
ANSWER: oracles
Summary
| 2023 UMN COOT | 08/19/2023 | Y | 3 | 16.67 | 100% | 67% | 0% |
Data
| BHSU | Our Job is Buzz | 10 | 10 | 0 | 20 |
| Jeff Weiner Fan Club | doubleplusnegfive | 10 | 10 | 0 | 20 |
| Palestrina Sawayama | Weird Klaus Barbie | 10 | 0 | 0 | 10 |