Overleg:NP-moeilijk

Johan Kwisthout 1 sep 2007 23:51 (CEST) Ik heb het artikel wat aangepast, met name de inleiding, en het een plaats gegeven in de serie over complexiteitstheorie en links naar anderstalige lemma's gemaakt. Wat mij betreft geeft deze beschrijving de noodzakelijke informatie weer om 'NP-moeilijk' van het bekendere 'NP-volledig' te omschrijven. Veel meer informatie toevoegen is vaak een duplicatie van wat er al bij NP-volledig te vinden is. Hoewel er natuurlijk altijd verbeteringen mogelijk zijn is het wat mij betreft geen 'werk in uitvoering' meer. Als iemand een andere mening is toegedaan, graag hier wat meer overleg hoe het artikel dan te verbeteren!

Ik zou ervoor zijn dit artikel met NP-volledig te kombineren. Ik heb de volgende veranderingen gemaakt:

Het is onbekend of NP=PSPACE (zie en.wikipedia.org), om een probleem te vinden dat niet NP is, moeten we dus naar een hogere klasse kijken, bijvoorbeeld EXPSPACE. Daar vinden we het "generalized chess" probleem.

Merk op dat de beste zet in gewone schaak een erg makkelijk probleem is: je kunt een tabel maken van alle stellingen en de beste zet in die stelling, en om de beste zet te vinden kijkt het algoritme gewoon in de tabel. Dat niemand weet hoe die tabel er uit ziet is een andere zaak, sommige algoritmen zijn moeilijk te schrijven. Dat we niet weten hoe het algoritme (de tabel) er uitziet betekent niet dat het niet bestaat.

Ik heb verwijderd dat elk probleem tot het stop-probleem gereduceerd kan worden. Het is wel waar, maar het voegt aan de duidelijkheid niets toe. (Het resultaat van de reductie is een programma dat eerst het originele probleem oplost en dan ofwel stopt, ofwel in een oneindige loop blijft hangen. Dat heeft niet de "smaak" van een reductie.)

Ik weet niet hoe ik in het nederlands met een bronvermelding moet omgaan, kan iemand dat voor mij doen? Helianthus 8 sep 2007 08:39 (CEST)

Johan Kwisthout 9 sep 2007 01:15 (CEST) Bij deze. Dank voor de verbeteringen; ik heb niet echt een mening over het al dan niet 'mergen' met NP-volledig. Feit was dat NP-moeilijk als zelfstandig lemma opgenomen (maar niet aangemaakt) was in dit artikel, en ik vond dat het onderwerp belangrijk genoeg was om er in ieder geval iets over te vertellen.

Johan Kwisthout 15 mei 2008 23:30 (CEST) Ik heb een verwijzing naar Integer Linear Programming opgenomen als 'schoolvoorbeeld' van een probleem waarbij het NP-moeilijkheidsbewijs niet zo 'moeilijk' is, maar het lidmaatschapsbewijs een stuk lastiger, dit ter illustratie van het gebruik van de term NP-moeilijk, al dan niet als 'tussenstap'. Als iemand een beter voorbeeld heeft - bijvoorbeeld waarbij het lidmaatschapsbewijs (nog) niet gegeven is - voel je vrij om het aan te passen!