quote:http://www.tweakers.net/nieuws/27147
Op dinsdag 27 mei 2003 15:40 schreef zim_ra het volgende:
Hallo kan iemand mij goed uitleggen hoe een quantumcomputer werkt of zo moeten werken en wat is Quantum entanglement..?
quote:
Quantum entanglement zorgt ervoor dat twee aparte deeltjes op een willekeurige afstand van elkaar, op hetzelfde moment, precies hetzelfde lot ondergaan. Tot voor kort lukte het wetenschappers alleen om dit verschijnsel op micrometerschaal plaats te laten vinden. Entanglement is cruciaal voor quantumcomputers, maar een afstand van enkele micrometers is niet voldoende.
[Dit bericht is gewijzigd door Brad op 27-05-2003 15:58]
quote:denk dat je beter ffies een paar jaar naar de UT kunt gaan . .. want ik vermoed dat het "gemiddelde" FoK! IQ niet zo ver gaat. . . (dat van mij iig niet)
hoe werkt quantummechanica en wat is quantum entanglement.. hoe snel wordt een pc dan..
Je kunt het ook niet vergelijken met de pc van nu. Nu doet een pc alles achterelkaar. Dan zou het mogelijk zijn om in verschillende demensies (toch ? ) een bewerking uit te voeren. Dus niet alleen in deze demensie waarin wij ons nu bevinden... klopt dit een beetje (heel simpel). Bij de pc is ook alles opgebouwd uit 0 en 1, bij een quantum pc kan dit 0 of 1 zijn of 0 en 1 tegelijk.
Klopt het ook niet dat bij elke beslissing die je maakt een nieuwe demensie ontstaat ??? naja dit is te moeilijk voor de 99,9999 % van de mensen om te begrijpen. Ik het het eens oooit mijn oom gevraagd (die er wel iets van snapt) maar het is heel moeilijk om uit te leggen.
Ik zou het zo zeggen, elke beveiliging die er ook bestaat op deze aarde... maakt niet uit met hoeveel bits encryptie is binnen een seconde (of minder) te kraken.. er heeft eens een stukje op tweakers hierover gestaan, ik zal eens zoeken.
Ik blijf dit topic eff volgen, is best wel leuk...
quote:Dat snappen die studiebollen daar ook niet. Daar moet je nog net iets slimmer voor zijn denk ik, maja ook het snappen hiervan is ook weer iets anders, zijn de geleerde er zelf eigenlijk al uit hoe het precies inelkaar zit ?
Op dinsdag 27 mei 2003 15:58 schreef Flierp het volgende:[..]
denk dat je beter ffies een paar jaar naar de UT kunt gaan . .. want ik vermoed dat het "gemiddelde" FoK! IQ niet zo ver gaat. . . (dat van mij iig niet)
quote:[punnikmode]
Op dinsdag 27 mei 2003 16:03 schreef Ruudje het volgende:
Hmm... dit is eigenlijk een onderwerp wat ik denk niemand echt hier zal begrijpen...Je kunt het ook niet vergelijken met de pc van nu. Nu doet een pc alles achterelkaar. Dan zou het mogelijk zijn om in verschillende demensies (toch ? ) een bewerking uit te voeren. Dus niet alleen in deze demensie waarin wij ons nu bevinden... klopt dit een beetje (heel simpel). Bij de pc is ook alles opgebouwd uit 0 en 1, bij een quantum pc kan dit 0 of 1 zijn of 0 en 1 tegelijk.
Klopt het ook niet dat bij elke beslissing die je maakt een nieuwe demensie ontstaat ??? naja dit is te moeilijk voor de 99,9999 % van de mensen om te begrijpen. Ik het het eens oooit mijn oom gevraagd (die er wel iets van snapt) maar het is heel moeilijk om uit te leggen.
Ik zou het zo zeggen, elke beveiliging die er ook bestaat op deze aarde... maakt niet uit met hoeveel bits encryptie is binnen een seconde (of minder) te kraken.. er heeft eens een stukje op tweakers hierover gestaan, ik zal eens zoeken.
Ik blijf dit topic eff volgen, is best wel leuk...
Het is dimensie
[/punnikmode]
quote:sorry zat eff in een andere dimensie
Op dinsdag 27 mei 2003 16:05 schreef Sjaakman het volgende:[..]
[punnikmode]
Het is dimensie
[/punnikmode]
quote:Quantum-mechanica en daarbij (deels) quantum computers komen al langs voor het eind van je 2e jaar Natuurkunde (at least in Utrecht). Maarja.. Quantum is al lang verouderd, string-theorie is the future..
Op dinsdag 27 mei 2003 16:05 schreef Ruudje het volgende:[..]
Dat snappen die studiebollen daar ook niet. Daar moet je nog net iets slimmer voor zijn denk ik, maja ook het snappen hiervan is ook weer iets anders, zijn de geleerde er zelf eigenlijk al uit hoe het precies inelkaar zit ?
quote:Je maakt al gebruik van quantummechanica bij het gebruik van al je elektronische apparatuur. Zonder quantummechanica zou de straling van een warm kopje koffie dodelijk zijn. Wat een onzin dus om te stellen dat quantummechanica verouderd zou zijn. Iedere keer als je koffie drinkt test je zelf de theorie.
Op dinsdag 27 mei 2003 16:14 schreef ZeroVince het volgende:[..]
Quantum-mechanica en daarbij (deels) quantum computers komen al langs voor het eind van je 2e jaar Natuurkunde (at least in Utrecht). Maarja.. Quantum is al lang verouderd, string-theorie is the future..
Stringtheorie is niet meer dan wat de naam zegt; een theorie, en nog geen eens de theorie. Pas als er praktische toepassingen of zelfs een eenvoudige voorspelling uit de Stringtheorie uit zou komen, dan heel misschien wel. De enige reden voor het bestaan van de Stringtheorie is het feit dat Quantummechanica geen gravitatie omvat. De filosofische vraag of gravitatie als fundamentele natuurkracht moet worden gezien is echter nog niet eens beantwoord.
Het is dus heel goed mogelijk dat de Stringtheorie niet meer dan een (verouderd) hersenspinsel is. 
Het effect zal wel opgewekt moeten worden door iets, en dus zal een quantumcomputer met 2 keer zoveel van die opwekdingen ook 2 keer zo snel zijn. zodoende hoeft een quantumcomputer niet oneindig snel te zijn. 
Dit alles in het geval dat een quantumcomputer werkt zoals in Ruudjes post beschreven.
Zie: http://www.rootnode.com/Members/cranmer/Wiki/QuantumComputing
Meer informatie over Quantumcomputing in het wfT-topic Informatieoverdracht sneller dan het licht..
quote:Ok gaat goed. Mooie verwijzingen.
Op dinsdag 27 mei 2003 19:17 schreef the.moderator het volgende:
Ik heb een paar jaar geleden zelf een encyclopedische webpublicatie over quantumcomputing gemaakt:Zie: http://www.rootnode.com/Members/cranmer/Wiki/QuantumComputing
Meer informatie over Quantumcomputing in het wfT-topic Informatieoverdracht sneller dan het licht..
Maar idd. o.a. http://qt.tn.tudelft.nl/~chiorescu/fluxqubit/ gaf een mooie uitleg (hoewel ik hoofdpijn krijg van al die formules).
quote:Daar bestaat maar één remedie voor. Namelijk een king-size bril. Ja, ik heb er ook één, het werkt echt.
Op dinsdag 27 mei 2003 22:12 schreef M.ALTA het volgende:[..]
...hoewel ik hoofdpijn krijg van al die formules.
Prof. David Deutsch (Oxford University) Prof. David K. Lewis (Princeton University) Dr. Peter Shor (AT&T Research)
Stel je voor dat je een voetbalveld onderverdeeld in kleine vierkantjes van 10 bij 10 cm. onder 1 vierkantje ligt een balletjes verstopt.
wil je dat balletje met en 'gewone ' pc vinden dan kijkt die pc 1 voor 1 onder die vierkantjes, dit kan dus wel even duren voordat die dat balletje heeft gevonden.en hoe sneller je pc, hoe sneller hij kan zoeken.
een quantum computer daarintegen kijkt gelijk onder alle vierkantjes, en zal dat balletje dus veel sneller vinden.
verder weet ik er weinig van af.
quote:Nee helaas zijn de exponentiële tijd problemen nog een te complexe rekenkundige klasse.
Op woensdag 28 mei 2003 07:56 schreef paladin het volgende:
kon je met quantumcomputers niet van van die mooie exponentiele problemen binnen niet-exponentiele tijd oplossen?
De complexiteitsverdeling van rekenkundige problemen - in afnemende complexiteit - is als volgt:
De klasse NP-Problems, hebben nog een verdere onderverdeling in NP-Hardness, maar NP-Complete omvat ze allemaal en geen systeem kan ze allemaal uitrekenen. Ook een Quantum Computer niet.
Enkele z.g. Non NP-Hard Problems waarschijnlijk wel, maar alleen een kleine subset ervan. Hoe klein die subset is weten we zelfs theoretisch nog niet. De teller staat nu nog maar op enkele specifieke typen, zoals Prime Factorization and Discrete Logarithms. Deze NP-Problems worden dan door de Quantum-Computer in Polynomial-time uitgerekend. We weten dat het theoretisch kan, omdat er Quantum-Algorithmen voor zijn geschreven. Zodra er dus meer Quantumalgorithmen, voor problemen uit die categorie zijn, zal de subset pas toenemen.
Waar die Quantumalgorithmen dus toe instaat moeten zijn is een vorm van declassificatie van de probleemcomplexiteit naar Polynomial-time (klasse P) problemen. De normale klasse P-Problems zijn eigenlijk verificatieproblemen van een soort waarbij de uitkomst al bekend is of verondersteld wordt. De verificatie van die uitkomst is dan in Polynomial-time mogelijk. Het "voetbalveld met verstopte balletjes" voorbeeld van * gebruikersnaam is zo'n simpel Polynomial-time Problem.
It's now a class P-Problem Scotty? "No problem Captain Kirk!"
De schrik voor de beveiligingsindustrie is nu dat de huidige cryptografie op factorisatie van priemgetallen gabaseerd is. Het kraken van een encryptiesleutel via het Quantumalgoritme voor Prime Factorization van Peter Shor kost daardoor geen miljoenen processors en miljoenen jaren meer. Het verhaal op Tweekers dat het nu in seconden kan klopt echter ook niet, want ook Polynomial-time problemen kunnen groot zijn.
Zoals je nu wel duidelijk zal zijn, blijven de nog complexere Exponential-time en Universal-time Problems praktisch en ook theoretisch nog steeds onoplosbaar. Helaas pindakaas.
[Dit bericht is gewijzigd door the.moderator op 28-05-2003 13:03]
quote:Niet als je een algoritme hebt gevonden dat evenzo een (negatief) exponentiele zoeksnelheid heeft (afh. van het NP-probleem uiteraard).
Op woensdag 28 mei 2003 09:20 schreef the.moderator het volgende:[..]
Nee helaas zijn de exponentiële tijd problemen nog een te complexe rekenkundige klasse.
v.b. probleem t orde complexiteit is exp(nt) ---> zoek een algoritme
met (neagtieve) katalysator exp(-nt) of sneller dempend in het aantal tussenberekeningen tot de eindoplossing.
quote:Bedankt voor het overzicht, dat weet ik dan ook weer.
De complexiteitsverdeling van rekenkundige problemen - in afnemende complexiteit - is als volgt:
Universal-time Exponential-time Non-deterministic Polynomial-time (NP) Complete Non-deterministic Polynomial-time (NP) Polynomial-time (P)
quote:Afhankelijk van het probleem (groote en de complexiteit) denk ik.
De klasse NP-Problems, hebben nog een verdere onderverdeling in NP-Hardness, maar NP-Complete omvat ze allemaal en geen systeem kan ze allemaal uitrekenen. Ook een Quantum Computer niet.
Voorbeeld: traveling salesman problem.
Afhankelijk van de randvoorwaarden van het model, kan men toch een
eindige (of lineaire) berekeningstijd vinden.
quote:De Laplace-transformatie en de
Enkele z.g. Non NP-Hard Problems waarschijnlijk wel, maar alleen een kleine subset ervan. Hoe klein die subset is weten we zelfs theoretisch nog niet. De teller staat nu nog maar op enkele specifieke typen, zoals Prime Factorization and Discrete Logarithms. Deze NP-Problems worden dan door de Quantum-Computer in Polynomial-time uitgerekend. We weten dat het theoretisch kan, omdat er Quantum-Algorithmen voor zijn geschreven. Zodra er dus meer Quantumalgorithmen, voor problemen uit die categorie zijn, zal de subset pas toenemen.
Bolzmann-machine kunnen soms wonderen verrichten/uitkomst bieden.
Worden die ook gebruikt bij Quantum-algoritmen om een polynomial-time af te dwingen ?
quote:leuke metafoor
Waar die Quantumalgorithmen dus toe instaat moeten zijn is een vorm van declassificatie van de probleemcomplexiteit naar Polynomial-time (klasse P) problemen. De normale klasse P-Problems zijn eigenlijk verificatieproblemen van een soort waarbij de uitkomst al bekend is of verondersteld wordt. De verificatie van die uitkomst is dan in Polynomial-time mogelijk. Het "voetbalveld met verstopte balletjes" voorbeeld van * gebruikersnaam is zo'n simpel Polynomial-time Problem.It's now a class P-Problem Scotty? "No problem Captain Kirk!"
quote:Daar ben ik een tijdje mee bezig geweest. De Mossad is er al met dit idee vandoor gegaan zie: DIGITAAL: M.ALTA eigen cryptosystemen bedenken en zie de posts van ChOAs.
De schrik voor de beveiligingsindustrie is nu dat de huidige cryptografie op factorisatie van priemgetallen gabaseerd is. Het kraken van een encryptiesleutel via het Quantumalgoritme voor Prime Factorization van Peter Shor kost daardoor geen miljoenen processors en miljoenen jaren meer. Het verhaal op Tweekers dat het nu in seconden kan klopt echter ook niet, want ook Polynomial-time problemen kunnen groot zijn.
quote:Niet zo snel opgeven.
Zoals je nu wel duidelijk zal zijn, blijven de nog complexere Exponential-time en Universal-time Problems praktisch en ook theoretisch nog steeds onoplosbaar. Helaas pindakaas.
quote:* Zelfs king-size brillen helpen niet meer. Nou dan maar een paardenmiddel om M.ALTA zoet te houden.
Op woensdag 28 mei 2003 15:57 schreef M.ALTA het volgende:[.. de formule-hoofdpijn van M.ALTA neemt extreme vormen aan ..]
Mathematical and Non Mathematical Properties of 17 .......... http://www.vinc17.org/d17_eng.pdf ..........
quote:Dacht het niet helemaal.
Op woensdag 28 mei 2003 09:20 schreef the.moderator het volgende:[..]
Nee helaas zijn de exponentiële tijd problemen nog een te complexe rekenkundige klasse.
v.b.
Probleem ~ n delen, rekentijd gewone iteratieve oplossing algoritme in
~ f(n) = c* exp(kn) stappen.
Truc: zoek een beter algoritme (dus G) dat garandeert:
rekentijd algoritme ~ a*n^q * G (f (n)) , zodat je een rekentijd in polynomial time van n hebt.
b.v. G (f(n)) = ln (f(n))
quote:Ik ken nog een onderverdeling (N = grootte probleem): tussen universele en exponentiele rekenproblemen.
De complexiteitsverdeling van rekenkundige problemen - in afnemende complexiteit - is als volgt:
Universal-time Exponential-time Non-deterministic Polynomial-time (NP) Complete Non-deterministic Polynomial-time (NP) Polynomial-time (P)
1) N^q exp (K*N) q integer, k konstant, q > N
2) N! exp (k*N) k konstant
3) N^q exp (k * N) q integer, k konstant, q<N
4) N!
3) & 4) zijn in het algemeen goed op te lossen binnen polynomial N based time (Bron: Philips Natlab).
Hoe ? bedrijfsgeheim, helaas (maar geen pindakaas).
quote:Je geeft hier zelf een voorbeeld van een Polynomial-time (class-P) probleem. Waarbij je in het begin zegt dat als je een onhandig algorithme gebruikt het eigenlijk een exponential-time problem is. Als je nu je afleiding niet van boven naar beneden, maar van beneden naar boven leest, dan zie je dat het probleem gewoon Polynomial-time is en blijft.
Op maandag 2 juni 2003 15:36 schreef M.ALTA het volgende:Dacht het niet helemaal.
v.b.
Probleem ~ n delen, rekentijd gewone iteratieve oplossing algoritme in~ f(n) = c* exp(kn) stappen.
Truc: zoek een beter algoritme (dus G) dat garandeert:
rekentijd algoritme ~ a*n^q * G (f (n)) , zodat je een rekentijd in polynomial time van n hebt.
b.v. G (f(n)) = ln (f(n))
Bewijs uit het ongerede: Neem een foutief algorithme dat door een bug in een oneindige loop komt. Dat maakt het probleem waar het algorithme voor bedoeld was niet plotseling een Universal-time problem. Dat zou dan dus de omgekeerde wereld zijn en dat is precies wat jij in dit natte vinger voorbeeld wel doet.
quote:Hier geldt exact hetzelfde. Je definieert eerst in 3. een exponentiële oplossingstijd in N bijvoorbeeld 2N seconden rekentijd. Dan zeg je vervolgens dat het via een andere methodiek (algorithme) ook in Polynomial-time bijvoorbeeld N2 berekent kan worden. Dan klopt of je uitgangsdefinitie niet of je hebt inmiddels een betere methode gevonden, waardoor je uitgangsdefinitie moet worden bijgesteld. Het probleem is en was dan altijd een Polynomial-time probleem. Het meest efficiënte algorithme is hiervoor bepalend.
Ik ken nog een onderverdeling (N = grootte probleem): tussen universele en exponentiele rekenproblemen.1) N^q exp (K*N) q integer, k konstant, q > N
2) N! exp (k*N) k konstant
3) N^q exp (k * N) q integer, k konstant, q<N
4) N!3) & 4) zijn in het algemeen goed op te lossen binnen polynomial N based time (Bron: Philips Natlab).
Hoe ? bedrijfsgeheim, helaas (maar geen pindakaas).
Er is nog een leuk openstaand probleem voor je. Hoeveel kleurpotloden van verschillende kleur heb je nodig om een kaart van alle landen te kunnen intekenen, zonder dat twee aan elkaar liggende landen dezelfde kleur krijgen. Ik stel voor dat we niet te overmoedig beginnen met een aantal landen N = 100.
quote:Ja, dat is juist, maar de truc/moeilijkheid zit hem in/ is om van een schijnbaar (b.v. a.g.v. onhandig algoritme) hopeloos NP-probleem, een beheersbaar (class-P) probleem te maken. Het gaat om het vinden van die G.
Op dinsdag 3 juni 2003 06:22 schreef the.moderator het volgende:[..]
Je geeft hier zelf een voorbeeld van een Polynomial-time (class-P) probleem. Waarbij je in het begin zegt dat als je een onhandig algorithme gebruikt het eigenlijk een exponential-time problem is. Als je nu je afleiding niet van boven naar beneden, maar van beneden naar boven leest, dan zie je dat het probleem gewoon Polynomial-time is en blijft.
quote:Nee, het gaat er om het oorspronkelijke probleem NP(n) met oplossing A te tranformeren (b.v. m.b.v. slimme transformaties) naar een probleem P(n) met oplossing B en dan direct uit B op A uit te komen via een terugherleiding.
Bewijs uit het ongerede: Neem een foutief algorithme dat door een bug in een oneindige loop komt. Dat maakt het probleem waar het algorithme voor bedoeld was niet plotseling een Universal-time problem. Dat zou dan dus de omgekeerde wereld zijn en dat is precies wat jij in dit natte vinger voorbeeld wel doet.
[..]
quote:Dat is niet zo direct te zeggen.
Hier geldt exact hetzelfde. Je definieert eerst in 3. een exponentiële oplossingstijd in N bijvoorbeeld 2N seconden rekentijd. Dan zeg je vervolgens dat het via een andere methodiek (algorithme) ook in Polynomial-time bijvoorbeeld N2 berekent kan worden. Dan klopt of je uitgangsdefinitie niet of je hebt inmiddels een betere methode gevonden, waardoor je uitgangsdefinitie moet worden bijgesteld. Het probleem is en was dan altijd een Polynomial-time probleem. Het meest efficiënte algorithme is hiervoor bepalend.
Het gaat er om, niet direct bij een hopeloze NP situatie te stellen dat het probleem een hopeloos lange oplossingsberekentijd nodig heeft.
quote:4, dit was wel heel makkelijk (doe ik zo uit mijn hoofd).
Er is nog een leuk openstaand probleem voor je. Hoeveel kleurpotloden van verschillende kleur heb je nodig om een kaart van alle landen te kunnen intekenen, zonder dat twee aan elkaar liggende landen dezelfde kleur krijgen. Ik stel voor dat we niet te overmoedig beginnen met een aantal landen N = 100.
Nu heb ik een vraagje voor jou:
Hoe kan het dat als je de maximum snelheid op een ononderbroken snelweg van 50 km lengte verhoogt van 120 km/h naar 140 km/h, dat de gemiddelde snelheid van alle vervoermiddelen die deze snelweg gebruiken DAALT, er van uitgaande dat alle bestuurders niet vrijwillig gas terug gaan nemen (en zonder dat er zich ongelukken voordoen).
quote:Whaa! simpel! tijd voor een leuke graaf die we gaan kleuren
Er is nog een leuk openstaand probleem voor je. Hoeveel kleurpotloden van verschillende kleur heb je nodig om een kaart van alle landen te kunnen intekenen, zonder dat twee aan elkaar liggende landen dezelfde kleur krijgen. Ik stel voor dat we niet te overmoedig beginnen met een aantal landen N = 100
Ehmm.. welke landen grenzen aan elkaar?
quote:Dit is misschien wel één van de moeilijkste wiskundige problemen met direkte praktische toepassing.
Op dinsdag 3 juni 2003 18:05 schreef paladin het volgende:[..]
Whaa! simpel! tijd voor een leuke graaf die we gaan kleuren
Ehmm.. welke landen grenzen aan elkaar?
quote:De toepassing is trouwens niet alleen voor atlassen en globes, maar ook voor meer zwaarwichtige zaken. Zoals lesroosters en spoorboekjes die nu nog steeds mathematisch vaak suboptimaal zijn geplanned.
Math Lecture: The Strong Perfect Graph Theorem by Maria Chudnovsky (CMI/Princeton University)Thursday, March 20, 2003 at 1:30 PM
Clay Mathematics Institute One Bow Street (4th Floor) Cambridge, MA 02138
Abstract
A graph is a set of vertices some pairs of which are joined by an edge and others are not. One of the properties of graphs studied in graph theory is graph coloring: color the vertices with as few colors as possible so that no two vertices with an edge between them receive the same color. Clearly, if a graph contains 10 vertices every two of which are joined by an edge, we need at least 10 colors in order to color it. However even that may not be enough. It has been a central questions in graph theory to characterize all graph for which it would be enough. In 1961 Claude Berge conjectured a possible characterization (that became known as The Strong Perfect Graph Conjecture), in 2002, in join work with Neil Robertson, Paul Seymour and Robin Thomas, we proved it. In my talk I will explain the problem more precisely and discuss some ideas used in the proof.
[Dit bericht is gewijzigd door the.moderator op 04-06-2003 01:59]
quote:Neen, een quantum computer rekent alsof iedere qubit een eigen processor is, niet in meerdere dimensies, door dat je dus meerdere qubits naast elkaar het werken, kun je taken parralele uitvoeren.
Op dinsdag 27 mei 2003 16:03 schreef Ruudje het volgende:
Hmm... dit is eigenlijk een onderwerp wat ik denk niemand echt hier zal begrijpen...Je kunt het ook niet vergelijken met de pc van nu. Nu doet een pc alles achterelkaar. Dan zou het mogelijk zijn om in verschillende demensies (toch ? ) een bewerking uit te voeren. Dus niet alleen in deze demensie waarin wij ons nu bevinden... klopt dit een beetje (heel simpel). Bij de pc is ook alles opgebouwd uit 0 en 1, bij een quantum pc kan dit 0 of 1 zijn of 0 en 1 tegelijk.
Klopt het ook niet dat bij elke beslissing die je maakt een nieuwe demensie ontstaat ??? naja dit is te moeilijk voor de 99,9999 % van de mensen om te begrijpen. Ik het het eens oooit mijn oom gevraagd (die er wel iets van snapt) maar het is heel moeilijk om uit te leggen.
Ik zou het zo zeggen, elke beveiliging die er ook bestaat op deze aarde... maakt niet uit met hoeveel bits encryptie is binnen een seconde (of minder) te kraken.. er heeft eens een stukje op tweakers hierover gestaan, ik zal eens zoeken.
Ik blijf dit topic eff volgen, is best wel leuk...
Een superpositie van zowel 0 en 1 alsmede een positie ertussen is aleen te vertalen naar de hedendaagse pc door iedere qubits te zien als een (oneindige maar iig hele lange) reeks (binaire)bits. Als een qubit 1 is, zijn alle binairebits ook 1 en vice versa, is een qubit een waarde tussen 0 en 1(bijv 0.5) dan worden er netvoveel bits omgeschakeld totdat je psies op de helft tussen 1(alle bits aan) en 0(alle bits uit)
Ik neem aan dat het duidelijk is dat rekenen met floating point getallen met enkele qubits sneller gaat dan met je nieuwe PIV @ 2800 mhz 
quote:Ik neem aan dat jij nog niet begrepen hebt hoe een Quantumcomputer werkt.
Op woensdag 4 juni 2003 09:57 schreef rey het volgende:Neen, een quantum computer rekent alsof iedere qubit een eigen processor is, niet in meerdere dimensies, door dat je dus meerdere qubits naast elkaar het werken, kun je taken parralele uitvoeren.
Een superpositie van zowel 0 en 1 alsmede een positie ertussen is aleen te vertalen naar de hedendaagse pc door iedere qubits te zien als een (oneindige maar iig hele lange) reeks (binaire)bits. Als een qubit 1 is, zijn alle binairebits ook 1 en vice versa, is een qubit een waarde tussen 0 en 1(bijv 0.5) dan worden er netvoveel bits omgeschakeld totdat je psies op de helft tussen 1(alle bits aan) en 0(alle bits uit)Ik neem aan dat het duidelijk is dat rekenen met floating point getallen met enkele qubits sneller gaat dan met je nieuwe PIV @ 2800 mhz
Een QC doet (nog) geen Floating Point bewerkingen. Daarvoor is een sequentiële von-Neumann architectuur nodig. Een QC kent geen von-Neumann architectuur en zelfs ook geen Booleaanse logica. Voor stapsgewijze aritmetiek zijn booleaanse logica en (tussen)registers noodzakelijk. Helaas heeft een QC zelfs geen registers, niet eens een klassieke flip-flop voor een aritmetische carry-bit. Er is dus ook geen enkele manier waarop je een QC kunt vergelijken met een klassieke computer zoals een PC.
Dat volgens jou een enkelvoudige Qubit vergelijkbaar zou zijn met een PC met oneindige aantal bits is ook de omgekeerde wereld. De Qubits van een QC staan niet opzichzelf, maar kunnen door de unitaire functionele componenten van de QC in superpositie worden gebracht. Zodra de Qubits via quantum entanglement in superpositie zijn gebracht zijn daarmee unitaire operaties mogelijk. Die operaties zorgen er dan voor dat er een statistisch gunstige kans ontstaat dat bij de ineenstorting van de superpositie het klassieke binaire antwoord (of niets) wordt gegeven.
quote:De door jou voorgestelde transformatie is al toegepast op Complexe Fourier Analyses en heeft de Fast Fourier Transform (FFT) opgeleverd. Er is echter geen voorgeschreven methodiek. Soms is iteratie sneller en soms is een niet iteratieve methode sneller. De methode die door de bank genomen de snelste oplossing geeft is bepalend voor de probleemcomplexiteit. Hier zijn ook vele praktische voorbeelden van, dus zijn theoretische welles nietes discussies in deze overbodig.
Op dinsdag 3 juni 2003 17:05 schreef M.ALTA het volgende:Nee, het gaat er om het oorspronkelijke probleem NP(n) met oplossing A te tranformeren (b.v. m.b.v. slimme transformaties) naar een probleem P(n) met oplossing B en dan direct uit B op A uit te komen via een terugherleiding.
quote:Wiskundigen houden zich niet met metafysica bezig. Ze houden er - met of zonder hoop - altijd rekening mee dat de snelste methode die bestaat toch nog verbeterd kan worden. Vandaar dat ze de complexiteit via reductie klassificeren. Een NP probleem wordt zodoende gedefinieerd als zijnde een probleem dat bewezen niet exponentieel is, maar waarvoor nog geen deterministisch polynomial-time oplossings-algoritme bestaat. Zodoende komt men dan uit op de klasse Non-deterministic Polynomial-time. Dat lijkt mij een nogal recht-toe recht-aan filosofie, maar helaas zie jij dat nog niet zo.
Dat is niet zo direct te zeggen.
Het gaat er om, niet direct bij een hopeloze NP situatie te stellen dat het probleem een hopeloos lange oplossingsberekentijd nodig heeft.
Vandaar dan ook dat je bij het eerste NP-Complete probleem dat ik je voorlegde al de mist in ging...
quote:Zoals ik al zei, was dit een NP-Complete probleem en het antwoord is dus fout. Als de landkaart een ruitjespatroon zou hebben, dan zou de oplossing 2 zijn, denk maar aan een schaakbord. Op een landkaart zijn er echter min of meer willekeurige raakvlakken tussen landen, zodat je dan meer dan 2 kleuren nodig hebt. Het Chromatic Number geeft het minimale aantal noodzakelijke kleuren en dat getal is echter afhankelijk van bepaalde topografische parameters.
4, dit was wel heel makkelijk (doe ik zo uit mijn hoofd).
Chromatic Number
The fewest number of colors y(G) necessary to color the vertices of a graph or regions of a surface (Skiena 1990, p. 210).
The chromatic number is the smallest positive integer z such that the chromatic polynomial Pi·G(z) > 0. Calculating the chromatic number of a graph is an NP-complete problem (Skiena 1990, pp. 211-212). Or, in the words of Harary (1994, p. 127), "no convenient method is known for determining the chromatic number of an arbitrary graph."
A graph with chromatic number two is said to be bicolorable, and a graph with chromatic number three is said to be three-colorable. In general, a graph with chromatic number n is said to be an n-chromatic graph, and a graph with chromatic number < n is said to be n-colorable.
quote:Je bent wel erg overmoedig, door ervanuit te gaan dat je antwoord op het NP-Complete probleem correct zou zijn, en gelijk maar een contraprobleem te formuleren. Mijn antwoord op jouw vraag is eigenlijk geen idee, maar ik zou het zelf zoeken in de toegenomen statistische spreiding in de voertuigsnelheden.
Nu heb ik een vraagje voor jou:Hoe kan het dat als je de maximum snelheid op een ononderbroken snelweg van 50 km lengte verhoogt van 120 km/h naar 140 km/h, dat de gemiddelde snelheid van alle vervoermiddelen die deze snelweg gebruiken DAALT, er van uitgaande dat alle bestuurders niet vrijwillig gas terug gaan nemen (en zonder dat er zich ongelukken voordoen).
Dat de statistische spreiding is toegenomen blijkt uit de gegeven parameters (met 20km verhoogde maximum snelheid en verlaagde gemiddelde snelheid). Gegeven de lengte van het gemeten traject van 50km, zal er ook sprake zijn van op en af-ritten met toegenomen snelheidsverschil. But I could be wrong!
En om weer back on-topic te komen is de bepaling van het Chromatic Number van een gegeven netwerk of Graph een prima kandidaat om mogelijk met een QC in Polynomial-time te worden opgelost. Als dat mogelijk zou blijken te zijn dan zou het time-table probleem, zoals bij lesroosters optimaal kunnen worden getackeld. Door inefficiënte roosters wordt veel geld verloren en ongemak geleden. Leslokalen en zelfs operatiekamers zouden veel efficiënter kunnen worden ingezet. Lege ziekenhuisbedden zouden dan tot het verleden behoren en er zou minder personeel ingeroosterd hoeven te worden. Wachtijden en het aantal overbodige overstappen bij de NS zou verminderen of misschien tot het verleden gaan behoren.
Dit lijkt mij een goede reden om het mathematisch inkleuren van grafieken serieuzer te gaan bekijken.
[Dit bericht is gewijzigd door the.moderator op 04-06-2003 18:42]
quote:Laplace Tr. is idd een veralgemenisering van de Fourier Tr./FFT.
Op woensdag 4 juni 2003 14:55 schreef the.moderator het volgende:[..]
De door jou voorgestelde transformatie is al toegepast op Complexe Fourier Analyses en heeft de Fast Fourier Transform (FFT) opgeleverd.
In een paar posts had ik het er over, niet zozeer om het in een algoritme te gebruiken, maar als hulpmiddel/bewijs om een methode/analogie/analoog probleem te vinden om de NP-problemen te herleiden naar P-problemen.
Als analogie gaf ik b.v. de Bolzmann-machine (een wiskundige model-machine voor het langzaam afkoelen van gas).
Het oplossen van het analoge probleem kan dan direct leiden tot
een herleiding van de oplossing van het NP-probleem, zelfs zodanig dat het oorspronkelijke NP-probleem gegarandeerd simpel P-probleem kan worden. Die garanties zijn te vinden in het gedrag van complexe processen (bijv. wet der grote aantallen, en structuur van de analoge herleiding).
quote:Heuristische methoden is een combinatie bijvoorbeeld.
Er is echter geen voorgeschreven methodiek. Soms is iteratie sneller en soms is een niet iteratieve methode sneller. De methode die door de bank genomen de snelste oplossing geeft is bepalend voor de probleemcomplexiteit. Hier zijn ook vele praktische voorbeelden van, dus zijn theoretische welles nietes discussies in deze overbodig.
[..]
quote:Voordat je pas dus tot een uitspraak van NP kunt komen:
Wiskundigen houden zich niet met metafysica bezig. Ze houden er - met of zonder hoop - altijd rekening mee dat de snelste methode die bestaat toch nog verbeterd kan worden. Vandaar dat ze de complexiteit via reductie klassificeren. Een NP probleem wordt zodoende gedefinieerd als zijnde een probleem dat bewezen niet exponentieel is, maar waarvoor nog geen deterministisch polynomial-time oplossings-algoritme bestaat. Zodoende komt men dan uit op de klasse Non-deterministic Polynomial-time. Dat lijkt mij een nogal recht-toe recht-aan filosofie, maar helaas zie jij dat nog niet zo.
NP-probleem: eerst te bewijzen is dus: ER IS GEEN deterministische polynomial-time oplossingsalgoritme bij een probleem.
Pas als dit BEWEZEN is kun je pas stellen dat het probleem NP is.
Het is veel moeilijker te bewijzen dat iets niet bestaat, dan te bewijzen dat iets wel bestaat.
quote:Ja maar 4 is altijd voldoende dacht ik.
Vandaar dan ook dat je bij het eerste NP-Complete probleem dat ik je voorlegde al de mist in ging...
[..]Zoals ik al zei, was dit een NP-Complete probleem en het antwoord is dus fout. Als de landkaart een ruitjespatroon zou hebben, dan zou de oplossing 2 zijn, denk maar aan een schaakbord. Op een landkaart zijn er echter min of meer willekeurige raakvlakken tussen landen, zodat je dan meer dan 2 kleuren nodig hebt. Het Chromatic Number geeft het minimale aantal noodzakelijke kleuren en dat getal is echter afhankelijk van bepaalde topografische parameters.
Chromatic Number
The fewest number of colors y(G) necessary to color the vertices of a graph or regions of a surface (Skiena 1990, p. 210).The chromatic number is the smallest positive integer z such that the chromatic polynomial Pi·G(z) > 0. Calculating the chromatic number of a graph is an NP-complete problem (Skiena 1990, pp. 211-212). Or, in the words of Harary (1994, p. 127), "no convenient method is known for determining the chromatic number of an arbitrary graph."
A graph with chromatic number two is said to be bicolorable, and a graph with chromatic number three is said to be three-colorable. In general, a graph with chromatic number n is said to be an n-chromatic graph, and a graph with chromatic number < n is said to be n-colorable.
[..]
quote:dan zoek je al aardig goed
Je bent wel erg overmoedig, door ervanuit te gaan dat je antwoord op het NP-Complete probleem correct zou zijn, en gelijk maar een contraprobleem te formuleren. Mijn antwoord op jouw vraag is eigenlijk geen idee, maar ik zou het zelf zoeken in de toegenomen statistische spreiding in de voertuigsnelheden.
quote:ook goed
Dat de statistische spreiding is toegenomen blijkt uit de gegeven parameters (met 20km verhoogde maximum snelheid en verlaagde gemiddelde snelheid). Gegeven de lengte van het gemeten traject van 50km, zal er ook sprake zijn van op en af-ritten met toegenomen snelheidsverschil. But I could be wrong!
quote:Je geeft idd heel gericht aan waar de toepassingen liggen.
En om weer back on-topic te komen is de bepaling van het Chromatic Number van een gegeven netwerk of Graph een prima kandidaat om mogelijk met een QC in Polynomial-time te worden opgelost. Als dat mogelijk zou blijken te zijn dan zou het time-table probleem, zoals bij lesroosters optimaal kunnen worden getackeld. Door inefficiënte roosters wordt veel geld verloren en ongemak geleden. Leslokalen en zelfs operatiekamers zouden veel efficiënter kunnen worden ingezet. Lege ziekenhuisbedden zouden dan tot het verleden behoren en er zou minder personeel ingeroosterd hoeven te worden. Wachtijden en het aantal overbodige overstappen bij de NS zou verminderen of misschien tot het verleden gaan behoren.
quote:idd, maar daar zal de politiek geen boodschap aan hebben, vrees ik.
Dit lijkt mij een goede reden om het mathematisch inkleuren van grafieken serieuzer te gaan bekijken.
Roosterplanning is goed te doen met heuristiek bij de aanpak van NP/P-roosterproblemen in de zorg.
Helaas is het bijv. in de zorg huilen met de pet op,
en van NP- of P-problemen heeft men daar nog nooit gehoord.
Men verhoogt liever de ziektekosten-premies.
Gegroet.
quote:Als jij van een reeds bestaand of nieuw klasse NP probleem kunt bewijzen dat er geen klasse P oplossings-algoritme voor kan bestaan, dan maak je per direkt kans om $1.000.000,- te ontvangen.
Op woensdag 4 juni 2003 20:39 schreef M.ALTA het volgende:...Voordat je pas dus tot een uitspraak van NP kunt komen:
NP-probleem: eerst te bewijzen is dus: ER IS GEEN deterministische polynomial-time oplossingsalgoritme bij een probleem.
Pas als dit BEWEZEN is kun je pas stellen dat het probleem NP is...
quote:Waar wacht je nog op? Of misschien nog beter, denk er nog eens over na...Millennium Prize Problems: P vs NP
Suppose that you are organizing housing accommodations for a group of four hundred university students. Space is limited and only one hundred of the students will receive places in the dormitory. To complicate matters, the Dean has provided you with a list of pairs of incompatible students, and requested that no pair from this list appear in your final choice. This is an example of what computer scientists call an NP-problem, since it is easy to check if a given choice of one hundred students proposed by a coworker is satisfactory (i.e., no pair from taken from your coworker's list also appears on the list from the Dean's office), however the task of generating such a list from scratch seems to be so hard as to be completely impractical. Indeed, the total number of ways of choosing one hundred students from the four hundred applicants is greater than the number of atoms in the known universe! Thus no future civilization could ever hope to build a supercomputer capable of solving the problem by brute force; that is, by checking every possible combination of 100 students. However, this apparent difficulty may only reflect the lack of ingenuity of your programmer. In fact, one of the outstanding problems in computer science is determining whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure. Problems like the one listed above certainly seem to be of this kind, but so far no one has managed to prove that any of them really are so hard as they appear, i.e., that there really is no feasible way to generate an answer with the help of a computer. Stephen Cook and Leonid Levin formulated the P (i.e., easy to find) versus NP (i.e., easy to check) problem independently in 1971.
Official Problem Description.pdf
Het is misschien toch verstandiger om je eerst in de wetenschappelijke theorie te verdiepen. Hier dus een link naar een Lecture by Blakemore Regents Professor Vijaya Ramachandran at University of Texas
P.S. Als goed bent in Minesweeper, dan heb je een groot voordeel, want je oplossing is daar dan ook op van toepassing.
quote:Boltzmann machines en heuristische zoekmethoden leveren niet gegarandeerd de beste oplossing en daar ben je wel naar op zoek. Bij het handelsreizigersprobleem, bijvoorbeeld, wil je de kortste route vinden, niet zo maar een korte route.
Op woensdag 4 juni 2003 20:39 schreef M.ALTA het volgende:
Laplace Tr. is idd een veralgemenisering van de Fourier Tr./FFT.In een paar posts had ik het er over, niet zozeer om het in een algoritme te gebruiken, maar als hulpmiddel/bewijs om een methode/analogie/analoog probleem te vinden om de NP-problemen te herleiden naar P-problemen.
Als analogie gaf ik b.v. de Bolzmann-machine (een wiskundige model-machine voor het langzaam afkoelen van gas).
Het oplossen van het analoge probleem kan dan direct leiden tot
een herleiding van de oplossing van het NP-probleem, zelfs zodanig dat het oorspronkelijke NP-probleem gegarandeerd simpel P-probleem kan worden. Die garanties zijn te vinden in het gedrag van complexe processen (bijv. wet der grote aantallen, en structuur van de analoge herleiding).
[..]Heuristische methoden is een combinatie bijvoorbeeld.
Dat NP-volledige problemen niet exact opgelost kunnen worden wil niet zeggen dat ze maar in de kast gezet moeten worden. Om toch iets aan dit soort problemen te doen kan je inderdaad heuristische methoden gebruiken om toch een best goede oplossing (hoewel niet gegarandeerd optimaal) te vinden. Voor het handelsreizigersprobleem kan je op deze wijze zeer goede oplossingen krijgen, zelfs al moet de handelsreiziger langs een miljoen steden gaan.
quote:Dit is niet waar. NP staat niet voor Non Polynomial, zoals jij lijkt te denken. Het staat voor Non-deterministic Polynomial. Om te bewijzen dat een probleem in NP zit moet je in polynomiale tijd kunnen laten zien dat een gegeven oplossing inderdaad goed is. Je kan lastig laten zien dat een oplossing inderdaad de optimale oplossing is, daarom wordt veelal de beslissingvariant van het probleem bekeken. Voor het handelsreizigersprobleem is dat: is er een route ter lengte x?
Voordat je pas dus tot een uitspraak van NP kunt komen:NP-probleem: eerst te bewijzen is dus: ER IS GEEN deterministische polynomial-time oplossingsalgoritme bij een probleem.
Pas als dit BEWEZEN is kun je pas stellen dat het probleem NP is.
Als je ook nog wilt laten zien dat een probleem NP-lastig is, moet je laten zien dat als je het probleem efficient kunt oplossen, dat je dan ook alle andere NP-lastige problemen efficient kunt oplossen.
Een probleem is NP-volledig als het in NP zit en ook nog eens NP-lastig is.
quote:Hier heb je inderdaad gelijk in!
Ja maar 4 is altijd voldoende dacht ik.
. Het is inderdaad zo dat dit kleuringsprobleem voor een willekeurige graaf lastig is. Voor planaire grafen (geen enkel 2-tal kanten kruist elkaar in het platte vlak) echter bestaat de vier kleuren stelling. Maar dan is het nog de vraag of het misschien niet met 2 of 3 kleuren kan. Hoe lastig dit is, weet ik niet. Met 4 kleuren kan het in ieder geval altijd.quote:We zeggen toch hier hetzelfde ?
Op vrijdag 6 juni 2003 19:35 schreef the.moderator het volgende:[..]
Als jij van een reeds bestaand of nieuw klasse NP probleem kunt bewijzen dat er geen klasse P oplossings-algoritme voor kan bestaan, dan maak je per direkt kans om $1.000.000,- te ontvangen.
[..]Waar wacht je nog op? Of misschien nog beter, denk er nog eens over na...
Ik zeg niet dat het absoluut bewezen kan worden, maar afhankelijk van bepaalde structuren van problemen (zie post wolfje)
quote:Maak je daar maar geen zorgen over, ik sluit mij aan bij wolfje.
Het is misschien toch verstandiger om je eerst in de wetenschappelijke theorie te verdiepen. Hier dus een link naar een Lecture by Blakemore Regents Professor Vijaya Ramachandran at University of Texas
quote:ook dat inkleur-raadsel van je.
P.S. Als goed bent in Minesweeper, dan heb je een groot voordeel, want je oplossing is daar dan ook op van toepassing.
quote:afh. van de strcutuur van het probleem, kun je soms garanties geven.
Op maandag 9 juni 2003 21:36 schreef Wolfje het volgende:[..]
Boltzmann machines en heuristische zoekmethoden leveren niet gegarandeerd de beste oplossing en daar ben je wel naar op zoek. Bij het handelsreizigersprobleem, bijvoorbeeld, wil je de kortste route vinden, niet zo maar een korte route.
quote:... idem
Dat NP-volledige problemen niet exact opgelost kunnen worden wil niet zeggen dat ze maar in de kast gezet moeten worden. Om toch iets aan dit soort problemen te doen kan je inderdaad heuristische methoden gebruiken om toch een best goede oplossing (hoewel niet gegarandeerd optimaal) te vinden. Voor het handelsreizigersprobleem kan je op deze wijze zeer goede oplossingen krijgen, zelfs al moet de handelsreiziger langs een miljoen steden gaan.
[..]
quote:idd niet alle; wel sommige die op het eerste gezicht hopeloos leken.
Dit is niet waar. NP staat niet voor Non Polynomial, zoals jij lijkt te denken. Het staat voor Non-deterministic Polynomial. Om te bewijzen dat een probleem in NP zit moet je in polynomiale tijd kunnen laten zien dat een gegeven oplossing inderdaad goed is. Je kan lastig laten zien dat een oplossing inderdaad de optimale oplossing is, daarom wordt veelal de beslissingvariant van het probleem bekeken. Voor het handelsreizigersprobleem is dat: is er een route ter lengte x?
Als je ook nog wilt laten zien dat een probleem NP-lastig is, moet je laten zien dat als je het probleem efficient kunt oplossen, dat je dan ook alle andere NP-lastige problemen efficient kunt oplossen.
quote:Ja, dit is een sterkere klassificatie van de probleem-set NP.
Een probleem is NP-volledig als het in NP zit en ook nog eens NP-lastig is.
[..]
Dit zal the.moderator wel in eerste instantie bedoeld hebben.
quote:iets met stelling van Fermat ? weet ik niet.
Hier heb je inderdaad gelijk in!
quote:Over wat voor garanties heb je het? Dat het mogelijk is om in polynomiale tijd de beste oplossing te vinden? Of heb je het over onder- en/of bovengrenzen voor het optimum?
Op dinsdag 10 juni 2003 22:11 schreef M.ALTA het volgende:afh. van de strcutuur van het probleem, kun je soms garanties geven.
[..]... idem
quote:wat bedoel je met idd niet alle? Ik heb naar mijn weten nergens in dat stukje "niet alle" gebruikt, dus er is geen grond om het me me eens te zijn.
idd niet alle; wel sommige die op het eerste gezicht hopeloos leken.
quote:ja, the.moderator gebruikt hiervoor de engelse terminologie voor: NP Complete. In het nederlands is dit NP volledig.
Ja, dit is een sterkere klassificatie van de probleem-set NP.
Dit zal the.moderator wel in eerste instantie bedoeld hebben.
Het is tot op heden nog niet gelukt om een NP volledig probleem op te lossen in polynomiale tijd. Het is de grote vraag of dit uberhaupt wel kan.
Merk goed op dat een NP volledig probleem in zijn algemeenheid is geformuleerd en dus geen concrete parameters heeft. Zo luidt het handelsreizigersprobleem: gegeven N steden en hun onderlinge afstanden, wat is dan de kortste route, waarbij de handelsreiziger eindigt in de beginstad, door alle steden? Er wordt hierbij absoluut niks gezegd over wat de afstand tussen stad A en stad B is.
Jouw opmerkingen slaan, zo heb ik de indruk, op specifieke instanties van NP volledige problemen. Er is dan bekend dat de afstand tussen stad A en stad B bijvoorbeeld 5 is. Het zou dan inderdaad kunnen dat voor deze specifieke instantie het probleem efficient op te lossen is (merk goed op dat dit lang niet altijd zo is!). Bijvoorbeeld als alle steden onderlinge afstand 1 hebben, of als je n.m steden gesitueerd op ( i, j ) met 0 < i < n en 0 < j < m en de onderlinge afstanden de euclidische afstanden zijn. Dit betekent dan echter niet dat je het NP volledige probleem hebt opgelost (waar het the.moderator om te doen is).
En, nogmaals, met heuristische methoden kan je inderdaad goede oplossingen vinden voor NP volledige problemen, het is echter niet te garanderen dat dit inderdaad de beste oplossingen zijn. Deze oplossingen kunnen toch heel bruikbaar zijn, maar je hebt er het NP volledige probleem niet mee opgelost.
quote:Nee, Fermat heeft er naar mijn weten weinig mee te maken. Het bewijs van deze stelling is nogal lang (enkele honderden pagina's). Er zijn wel voorlopers van deze stelling, te weten de 6 kleuren stelling en de 5 kleuren stelling, die een stuk makkelijker te bewijzen zijn.
iets met stelling van Fermat ? weet ik niet.
quote:Soms is een probleem zodanig geformuleerd, dat je het bepaalde eigenschappen heeft die je kunt gebruiken in een slim algortime..
Op woensdag 11 juni 2003 00:14 schreef Wolfje het volgende:[..]
Over wat voor garanties heb je het? Dat het mogelijk is om in polynomiale tijd de beste oplossing te vinden? Of heb je het over onder- en/of bovengrenzen voor het optimum?
[..]
B.v. handelsreizigersprobleem:
eigenschap: alle onderlinge afstanden verschillen van elkaar met lengte precies 1, dit maakt het probleem veel eenvoudiger.
quote:het was een dubbele ontkenning in een interpretatie..
wat bedoel je met idd niet alle? Ik heb naar mijn weten nergens in dat stukje "niet alle" gebruikt, dus er is geen grond om het me me eens te zijn.
[..]
quote:Ik denk het wel voor specifieke NP-volledige problemen (dus niet alle; ik beweer/vermoed dus hiermee dat ook in de set van NP-volledige problems er een gedetailleerder registreerbare gradatie is, van moeilijk tot hopeloos moeilijk).
ja, the.moderator gebruikt hiervoor de engelse terminologie voor: NP Complete. In het nederlands is dit NP volledig.Het is tot op heden nog niet gelukt om een NP volledig probleem op te lossen in polynomiale tijd. Het is de grote vraag of dit uberhaupt wel kan.
Als heuristische methoden worden uitgesloten:
Ik denk dat men het moet zoeken in de algebra en de discrete wiskunde in combinatie met de vector-calculus en complexe golf-functies.
Dit is alleen een vermoeden, ik heb absoluut geen concrete aanwijzingen hiervoor.
quote:bekend.
Merk goed op dat een NP volledig probleem in zijn algemeenheid is geformuleerd en dus geen concrete parameters heeft. Zo luidt het handelsreizigersprobleem: gegeven N steden en hun onderlinge afstanden, wat is dan de kortste route, waarbij de handelsreiziger eindigt in de beginstad, door alle steden? Er wordt hierbij absoluut niks gezegd over wat de afstand tussen stad A en stad B is.
quote:Dit heb ik in andere woorden min of meer ook gesteld in dit topic.
Jouw opmerkingen slaan, zo heb ik de indruk, op specifieke instanties van NP volledige problemen. Er is dan bekend dat de afstand tussen stad A en stad B bijvoorbeeld 5 is. Het zou dan inderdaad kunnen dat voor deze specifieke instantie het probleem efficient op te lossen is (merk goed op dat dit lang niet altijd zo is!). Bijvoorbeeld als alle steden onderlinge afstand 1 hebben, of als je n.m steden gesitueerd op ( i, j ) met 0 < i < n en 0 < j < m en de onderlinge afstanden de euclidische afstanden zijn. Dit betekent dan echter niet dat je het NP volledige probleem hebt opgelost (waar het the.moderator om te doen is).
quote:Nee garanties niet, maar bij Philips Natlab en IBM heeft men toch heel wat schijnbare NP-volledige klassificaties gekraakt.
En, nogmaals, met heuristische methoden kan je inderdaad goede oplossingen vinden voor NP volledige problemen, het is echter niet te garanderen dat dit inderdaad de beste oplossingen zijn. Deze oplossingen kunnen toch heel bruikbaar zijn, maar je hebt er het NP volledige probleem niet mee opgelost.
[..]
Het probleem is weer: bewijzen dat iets niet kan, is moeilijker dan te bewijzen dat iets wel kan.
v.b. handelsreizigersprobleem: rekentijd: evenredig met N!
wie weet dat er een gegarandeerde truc te verzinnen is dat de rekentijd kan worden gereduceerd tot evenredig met Log (N!) ~ N log (N) <~ N^2
quote:Als ik gepensioneerd ben en tijd zat heb, wellicht dat ik dan dit bewijs eens ga nalezen.
Nee, Fermat heeft er naar mijn weten weinig mee te maken. Het bewijs van deze stelling is nogal lang (enkele honderden pagina's). Er zijn wel voorlopers van deze stelling, te weten de 6 kleuren stelling en de 5 kleuren stelling, die een stuk makkelijker te bewijzen zijn.