ECCC-Report TR21-181https://eccc.weizmann.ac.il/report/2021/181Comments and Revisions published for TR21-181en-usThu, 30 Dec 2021 17:37:31 +0200
Paper TR21-181
| The KW Games as a Teaser |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2021/181This is a purely pedagogical text.
We advocate using KW-games as a teaser (or ``riddle'') for a complexity theoretic course.
In particular, stating the KW-game for a familiar NP-complete problem such as 3-Colorability and asking to prove that it requires more than polylogarithmic communication poses a seemingly tractable question that requires no background.
The fact that this is actually a formidable question puts much of complexity theory in the right perspective.
Indeed, complexity theory contains numerous extremely appealing problems that require little background (beyond basic comfort with the notion of computation) and yet are formidable.
Thu, 30 Dec 2021 17:37:31 +0200https://eccc.weizmann.ac.il/report/2021/181