Packet 2: Bonus 17

The seminal text Computers and Intractability by Garey and Johnson is primarily about studying computational problems with this property. For 10 points each:
[10m] Name this property of 21 problems proposed by Richard Karp. The Boolean satisfiability problem has this property by the Cook–Levin theorem.
ANSWER: NP-complete [or NPC; prompt on NP or NP-hard]
[10e] Many of the NP-complete problems on Karp’s list concern these mathematical objects, such as whether they can be colored by at most three colors.
ANSWER: graphs [accept planar graphs]
[10h] These small abstract units are often used to construct reductions to NP-complete problems. For the reduction of 3-COLOR to 3-SAT, one can construct these units as specific graphs for each variable and operation, then link them together.
ANSWER: gadgets [prompt on components]
<Editors, Other Science> | K. Playoffs 2 (Editors 2)

HeardPPBE %M %H %
2314.3578%57%9%

Back to bonuses

Conversion

TeamOpponentPart 1Part 2Part 3TotalParts
British ColumbiaTexas1010020ME
BruinStanford B1010020ME
CambridgeGeorgia Tech C010010E
Chicago AMaryland A1010020ME
Chicago BNorthwestern B010010E
Columbia AHarvard1010020ME
Columbia BGeorgia Tech B1010020ME
GeorgetownCornell010010E
Illinois AUCLA1010020ME
Illinois BNorth Carolina010010E
MITMinnesota10101030MEH
MichiganVirginia010010E
Penn StateJohns Hopkins100010M
PurdueBrown0000
RutgersOhio State0000
Toronto AIndiana10101030MEH
UC Berkeley ANorthwestern A1010020ME
UC Berkeley BStanford A1010020ME
UCFSwarthmore1010020ME
VanderbiltToronto B010010E
Virginia TechNYU A0000
WashUPittsburgh100010M
WaterlooMaryland B010010E

Summary

TournamentEditionMatchHeardPPBE %M %H %
Main Site2026-04-17✓2314.3578%57%9%