Computational problems without computation

Gerhard Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

41 Downloads (Pure)

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 languageDutch
Pages (from-to)140-147
Number of pages8
JournalNieuw archief voor wiskunde
VolumeS 5, dl 4
Issue number2
Publication statusPublished - 2003

Keywords

  • IR-85540
  • METIS-213304

Cite this