Computational problems without computation

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

Problemen uit de discrete wiskunde lijken op het eerste gezicht vaak erg simpel. Ze kunnen meestal gemakkelijk en zonder gebruik te maken van wiskundige begrippen worden geformuleerd. Toch komt het vaak voor dat zo’n ogenschijnlijk eenvoudig probleem nog open is of dat er, zoals bij het handelsreizigersprobleem, wel een oplossing gegeven kan worden,maar alleen een die onbruikbaar is omdat de rekentijd bij grotere getallen te snel groeit. In dit artikel, gebaseerd op zijn voordracht op het NMC 2002, kijkt Gerhard Woeginger naar de tegenovergestelde situatie. Hij introduceert allerlei discrete problemen die onoplosbaar lijken, maar waarvoor er een simpele oplossing bestaat.
Original languageEnglish
Pages (from-to)140-147
JournalNieuw Archief voor Wiskunde
Volume5/4
Issue number2
Publication statusPublished - 2003

Fingerprint

Dive into the research topics of 'Computational problems without computation'. Together they form a unique fingerprint.

Cite this