Blob lost handelsreizigerprobleem op

[Math-E-Mad-X]

Ja, maar dat is eigenlijk valsspelen. Het wiskundige probleem is namelijk of het met een Turing-machine mogelijk is om NP-problemen in polynomiale tijd te berekenen.


Of de natuur dat kan is weer een heel ander vraagstuk.

[317070]

Zo stel ik mij ook voor dat de oplossing van het handelsreizigerprobleem zonder haperen uit een proefopstelling moet rollen, zodra we er in slagen een situatie te bedenken waarin de natuur noodzakelijkerwijs het handersreizigerprobleem moet oplossen om te weten wat haar te doen staat.

Nee, dat klopt. De vraag momenteel is of het met een Turing-machine snel (in polynomiale tijd) valt op te lossen. Als we bijvoorbeeld een kwantumopstelling mogen gebruiken, dan kunnen we het wel in polynomiale tijd oplossen. http://www.sciencedirect.com/science/article/pii/S1386947702009281


Overigens is het meer dan het vinden van een zuinige auto. Erg veel problemen in onze wereld kunnen we erg goed simuleren. Design komt dan eigenlijk neer op het vinden van de beste oplossing in een simulatie. Design valt dus te automatiseren, zolang je maar 'snel' een goede oplossing vindt. Problemen als de travelling salesman tonen aan dat dit niet zo is, waardoor er veel interesse is om die problemen te tackelen. Als we design kunnen automatiseren, dan hebben we automatisch de zuinigste motoren, de efficiëntste circuits en het beste verkeersplan voor een stad.

[Bartjes]

Nee, dat klopt. De vraag momenteel is of het met een Turing-machine snel (in polynomiale tijd) valt op te lossen. Als we bijvoorbeeld een kwantumopstelling mogen gebruiken, dan kunnen we het wel in polynomiale tijd oplossen. http://www.sciencedi...386947702009281

OK - het bestaat dus al.