Memcomputer verwerkt data op vergelijkbare manier als mensel

[H!GHGuY]

Als een normale computer, of deterministische Turingmachine, een NP-volledigheidsprobleem moet oplossen, zoals het handelsreizigersprobleem, gaat de benodigde processorkracht en geheugen kwadratisch omhoog als het aantal punten waar de 'handelsreiziger' langs moet, toeneemt.

Dit zou een complexiteit van O(n²) impliceren wat volgens mij enerzijds niet klopt en anderzijds als P-probleem zou aanzien worden.

De brute-force methode zou echter O(n!) zijn en er zijn oplossingen die O(n² * 2^n) zijn. Deze zijn niet polynomiaal meer.

[GlowMouse]

Ik zou niet zomaar uitspraken doen over de tijdscomplexiteit, want voor NP-volledige problemen is die onbekend.
Het woord "NP-volledigheidsprobleem" komt in het artikel voor, waar "NP-volledig probleem" wordt bedoeld. De term NP-volledigheidsprobleem is onzuiver omdat ermee ook het probleem of P=NP kan worden aangeduid.

[svandewouw]

gelimiteerden => gelimiteerd en

[letatcest]

Ik had het niet zo handig hertaald naar een - voor mijn idee - lopende zin. Desalniettemin is het aangepast en nog wat 'mogelijk' en 'ooit' en 'misschien' toegevoegd. Het betreft ten slotte een proof-of-concept.

[ Voor 32% gewijzigd door letatcest op 03-07-2015 22:59 ]

[GlowMouse]

Nu staat er:

Theoretisch kan deze computer kan problemen wel in korte tijd oplossen.

En in dit stuk:

Als een normale computer, of deterministische Turingmachine, een NP-volledig probleem moet oplossen, zoals het handelsreizigersprobleem, gaat de benodigde processorkracht en geheugen heel snel omhoog als het aantal punten waar de 'handelsreiziger' langs moet, toeneemt.

is 'heel snel' niet bewezen. Het zou zelfs lineair kunnen schalen, net als de memcomputer.

[letatcest]

GlowMouse schreef op vrijdag 03 juli 2015 @ 23:17:
Nu staat er:

[...]

En in dit stuk:

[...]

is 'heel snel' niet bewezen. Het zou zelfs lineair kunnen schalen, net als de memcomputer.

Je hebt gelijk. Aanpassingen doen om tien voor elf 's avonds is nooit handig