NP compleetheid van het 3 kleuren probleem

[Verwijderd]

We hebben het nu op school over NP-compleetheid, en er wordt daarbij vanuit gegaan dat het 3 kleuren probleem NP compleet is, maar dat wordt nergens bewezen en ik kan er ook niets over op internet vinden. Heeft iemand een idee hoe je kan bewijzen dat het 3 kleuren probleem NP compleet is?

[Morphs]

Waar HEB je het over? Kun je je huiswerk-vraag eens wat duidelijker uiteenzetten (wat is NP-compleetheid bijv?)?

[Pooh]

Heb het bewijs wel thuis liggen, mail me maar voor details.

[Verwijderd]

De standaard manier om NP-compleetheid van een taal L te bewijzen is een bestaande NPC taal N te vinden die makkelijk reduceerbaar is (via Karp-reductie) naar je taal L. Als je N naar L kunt reduceren is L ook NPC. Je kunt het ook moeilijk doen, via het originele bewijs van Cook, maar daar is geen beginnen aan.

[FCA]

Verder: Wat is het 3 kleuren probleem?
Ik heb wel van het 4 kleuren probleem gehoord, maar het 3 kleuren probleem ken ik niet.

[Confusion]

Op woensdag 13 februari 2002 19:08 schreef FCA het volgende:
Verder: Wat is het 3 kleuren probleem?
Ik heb wel van het 4 kleuren probleem gehoord, maar het 3 kleuren probleem ken ik niet.

Het is de simpelere versie ervan

[Diadem]

Waar gaat dit in hemelsnaam over?

[Verwijderd]

Op woensdag 13 februari 2002 19:15 schreef Fused het volgende:
Het is de simpelere versie ervan

Het 3-kleuren probleem begon idd. als 4-kleuren probleem, maar ondertussen is het 4-kleuren (en 2-kleuren) probleem opgelost (en is triviaal in de complexiteitsleer). Voor 3 kleuren geldt dat echter niet, dit is een zeer complex probleem.

Voor de mensen die geen algoritmiek gehad hebben: Het gaat hier over het bepalen van de complexiteitsklasse van een algoritmisch probleem. NP betekent dat het probleem niet (door een deterministische automaat) in polynomiale tijd is op te lossen, NPC is een deelklasse van de zwaarste NP problemen. Het X-kleuren probleem houdt in dat je ja of nee moet antwoorden op de volgende vraag: kun je een willekeurige landkaart met X kleuren inkleuren zodat nooit twee landen met de zelfde kleur elkaar raken?

<edit>
NP staat officieel voor non-deterministic polynomial, een non-deterministische automaat kan deze problemen dus wel in polynomiale tijd oplossen. (Voordat de puristen over me heenvallen )
</edit>

[Diadem]

Op woensdag 13 februari 2002 20:39 schreef mietje een uitleg:

Ow, dat. Zeg dat dan!

Ik vermoede al zoiets, maar wist het niet zeker.

Tsja, bewijzen kan ik dit niet ben ik bang. Ik ken wel een aantal algoritmes om zo'n landkaart te maken. Maar deze zijn Brute Force, dus tsja ....

Iig is dit probleem Brute Force op te lossen met een eindig algoritme. Dus je kunt altijd het antwoord geven op de vraag die mietje stelt. Al zul je eventjes bezig zijn in het slechtste geval....

[Verwijderd]

Op woensdag 13 februari 2002 20:58 schreef Diadem het volgende:
Iig is dit probleem Brute Force op te lossen met een eindig algoritme. Dus je kunt altijd het antwoord geven op de vraag die mietje stelt. Al zul je eventjes bezig zijn in het slechtste geval....

Je moet de vraag voor elke denkbare kaart beantwoorden, dus het zal toch wel ff gaan duren vrees ik Naar ik mij meen te herinneren is het 4-kleuren probleem opgelost door het als formele taal te specificeren en vervolgens een uitzonderingsklasse te bepalen van speciaal moeilijk op te lossen kaarten. Die uitzonderingsklasse (iets van 1700 leden dacht ik) is toen geheel brute force doorgerekend.

Lichtelijk offtopic: dit is dus een staaltje van een formeel bewijs "nieuwe stijl", waarbij er serieus gebruik wordt gemaakt van computers. Als je werkelijk wilt nagaan of het bewijs geldig is moet je niet alleen controleren of de wiskunde klopt, maar de programmatuur van de computers moet ook foutloos zijn!

[FCA]

Op woensdag 13 februari 2002 21:23 schreef mietje het volgende:

[..]

Je moet de vraag voor elke denkbare kaart beantwoorden, dus het zal toch wel ff gaan duren vrees ik Naar ik mij meen te herinneren is het 4-kleuren probleem opgelost door het als formele taal te specificeren en vervolgens een uitzonderingsklasse te bepalen van speciaal moeilijk op te lossen kaarten. Die uitzonderingsklasse (iets van 1700 leden dacht ik) is toen geheel brute force doorgerekend.

Lichtelijk offtopic: dit is dus een staaltje van een formeel bewijs "nieuwe stijl", waarbij er serieus gebruik wordt gemaakt van computers. Als je werkelijk wilt nagaan of het bewijs geldig is moet je niet alleen controleren of de wiskunde klopt, maar de programmatuur van de computers moet ook foutloos zijn!

Ah... maar dit is dus een ander probleem.
En dat is zeker niet triviaal. Veel wiskundigen accepteren het bewijs niet eens, het is niet slim, eigenlijk gewoon bot rekenen en niet te controleren.
Hoewel ik zelf ook wel bewijzen produceer op deze manier en ik steeds meer bewijzen op die manier zie.

En dit is dus iets anders als het bepalen of voor een bepaalde landkaart x kleuren voldoende zijn, en hoe moeilijk dat voor een willekeurige landkaart is.

[Verwijderd]

Op woensdag 13 februari 2002 21:38 schreef FCA het volgende:
En dat is zeker niet triviaal.

Het is triviaal in de algoritmiek/complexiteitsleer. De oplossing mag enorm moeilijk zijn, als hij gevonden is wordt het probleem triviaal. <edit>maw. 1700 gevallen doorrekenen is iets anders dan niet weten waar je beginnen moet</edit>

Veel wiskundigen accepteren het bewijs niet eens, het is niet slim, eigenlijk gewoon bot rekenen en niet te controleren. Hoewel ik zelf ook wel bewijzen produceer op deze manier en ik steeds meer bewijzen op die manier zie.

Dat punt wilde ik (een beetje offtopic) aansnijden, het werkt niet alleen zo in de wiskunde, maar in veel meer wetenschappen. Het zelfstandig natrekken van formele bewijzen in de wetenschap wordt zo iets van het verleden en is enkel weggelegd voor kapitaalkrachtige onderzoeksinstellingen met grote rekencentra; de gewone "boerenkool-wetenschapper" moet het maar aannemen en kan niet meer aan peer-review doen.

En dit is dus iets anders als het bepalen of voor een bepaalde landkaart x kleuren voldoende zijn, en hoe moeilijk dat voor een willekeurige landkaart is.

Oeps, ik beter elke willeurige kaart kunnen schrijven.

[Verwijderd]

Sorry voor mijn late reactie, maar jullie hadden gelijk over mijn vraag. Ik heb Poorbear ondertussen ook gemaild, voor het bewijs. Alvast bedankt.

[RickN]

Op woensdag 13 februari 2002 20:39 schreef mietje het volgende:

[..]

Voordat de puristen over me heenvallen

VANONDERUH!!!!!

In dit geval ga ik denk ik toch maar even de purist uithangen , want je maakt toch een redelijk cruciale fout hier.

(Echt puristisch zal ik maar niet worden, want dan zou ik alles in termen van talen en beslisbaarheid moeten gaan vertellen en daar heb ik zelf een hekel aan.)

De definitie van NP is niet wat door veel mensen wordt gedacht, nl. de problemen die niet in polynomiale tijd door een deterministische machine op te lossen zijn. Dit zou namelijk betekenen dat deze klasse van problemen disjunct is met de klasse P, de klasse van problemen die WEL in polynomiale tijd door een deterministische machine op te lossen zijn. Dat zou betekenen dat P <> NP en dat is nog helemaal niet bewezen (wel zeer waarschijnlijk overigens).

De goede definitie van de klasse NP is als volgt:

NP is de klasse van beslissings problemen die in polynomial tijd verifieerbaar zijn door een DFA.

Een equivalente definitie (ook aangestipt door mietje):
NP is de klasse vn beslissings problemen die in polynomiale tijd beslisbaar zijn door een NFA (Nondeterministic Finite Automata).

Wat is dan verifieerbaarheid? Nou, dat is gegeven een oplossing bepalen of die oplossing ook echt een oplossing is.

Voorbeeldje: Het bepalen of een getal composiet is (d.w.z. factoren heeft) zit in de klasse NP. Niemand weet nog zeker of er een polynomiaal algoritme bestaat om dit te bepalen, maar het probleem is wel snel te verifieren, nl. als je mij een oplossing (deler) geeft, kan ik door een simele snelle deling bepalen of het ook echt een deler is.

En wat is NP-compleet?

NP compleet is de klasse van problemen die:
1. In de klasse NP zit (duh)
2. Elk probleem in NP is in polynomial tijd reduceerbaar tot elk probleem in NP-compleet.

Wat betekent "reduceerbaar"?
Kort door de bocht.
Een probleem A is reduceerbaar tot een probleem B als je A kunt omschrijven tot een instantie van het probleem B. Als je dan B kunt oplossen heb je gelijk ook A opgelost.

Wat is er leuk aan de klasse NP-compleet?
Als je een probleem in de klasse NP-compleet in polynomiale tijd kunt oplossen (op een DFA natuurlijk) dan kun je ELK probleem in NP in polynomiale tijd oplossen. Want elk probleem A in NP kan in polynomiale tijd worden omgeschreven tot een probleem B in NP-compleet. Polynomiale tijd voor het omschrijven van A naar B + polynomiale tijd voor het oplossen van B = polynomiale tijd in totaal voor het oplossen van A.

Wat moet je hiervan onthouden?
NP <> niet oplosbaar in polynomiale tijd op een DFA.

[Verwijderd]

Sorry dat ik dit topic weer om hoog kick, maar, poohbear, ik heb je vorige week al een mailtje gestuurd naar het adres in je profiel en geen reactie gehad. Als je tegenwoordig een ander emailadres hebt, kan je me bereiken onder: [e-mail] .

[RickN]

Deze vraag staat als opgave in een boek dat ik heb. Ze noemen het daar het 3COLOR probleem. Ik zal eens kijken of ik deze opgave zelf kan oplossen.

Ik denk dat je bij je bewijs ervan uit mag gaan dat 3COLOR in NP zit, maar voor de zekerheid zal ik hier even bewijzen dat dat zo is.

Zoals ik al eerder poste zit een probleem in NP als er een polynomiale tijd verifier voor is. Om te bewijzen dat 3COLOR in NP zit, moet je dus zo'n verifier geven.

Gegeven een kleurtoekenning voor alle knopen in de graaf.
Tel het aantal kleuren dat gebruikt wordt, als dit <> 3 is, return "reject"
Test voor elke knoop in de graaf of zijn kleur verschilt van de kleur van al z'n buren, zo ja, return "accept", anders return "reject".

De eerste stap in dit algoritme kost O(V) stappen. De tweede kost max O(N^2) stappen, het hele algoritme kost dus O(N^2 + N) stappen en dat is polynomiaal, dus 3COLOR zit in NP.

Ik ga nu (een ieder geval een opzetje voor) een bewijs van de NP-compleetheid van 3COLOR geven.

Wordt vervolgt.

[vervolg]

Vanuit het niets bewijzen dat een een probleem NP-compleet is, is een irritant karweitje. Je moet dan namelijk laten zien dat elk probleem in NP in polynomiale tijd reduceerbaar is tot jouw probleem. Dat ga ik hier niet doen, als je zo'n bewijs zoekt raad ik je aan een goed boek te zoeken. Zelf heb ik "Introduction to the Theory of Computation" van Michael Sipser gebruikt.

Als je er in je bewijs gebruik van mag maken dat er andere NP-complete problemen zijn, en nog belangrijker, je van één specifiek probleem mag aannemen dat het NP-compleet is, wordt je bewijs ineens een stuk eenvoudiger. Je hoeft dan namelijk alleem maar te laten zien dat dat NP-complete probleem in polynomiale tijd reduceerd tot het probleem waarvan je de NP-compleetheid moet aantonen.

Uit de hint in de opgave in het boek dat ik gebruik maak ik op dat de NP-compleetheid van het 3SAT probleem een goede keuze is om in dit bewijs als aanname te doen.

Het 3SAT probleem is het volgende:
Is het mogelijk om aan de variabelen in een booleanse expressie, in conjunctive normaal vorm met precies 3 literals in elke clause, een toekenning te doen zo dat de expressie tot TRUE evalueert. (Als dit onduidelijk is moet je even op internet zoeken naar de onduidelijke termen)
B.V. (a or ~b or x) and (~z or f or b) and (~a or ~f or v) and enz.

Hoe je vervolgens een willekeurige instantie van het 3SAT probleem omschrijft naar een instantie van het 3COLOR probleem laat ik aan jou over. Ik was hier mee bezig maar google was me voor hint hint hint...

[Verwijderd]

Ze claimden bij ons dat het checken kan in O(|V|+|E|) (V = knopen, E = zijden), maar dat wordt ook nergens bewezen.

/mijn idee:
Je gaat namelijk de knopen af om kleuren te tellen, dat kost O(|V|), en vervolgens ga je alle zijden af om te kijken of de eindpunten van 1 zijde verschillend gekleurd zijn, dat kost O(|E|). Wat dus totaal O(|V|+|E|) kost, zodat hij inderdaad in polynomiale tijd te controlen is. Wat betekent dat 3COLOR (of hoe je het ook wilt noemen) NP compleet is.

[RickN]

Op maandag 18 februari 2002 19:34 schreef DennisBergen het volgende:
Ze claimden bij ons dat het checken kan in O(|V|+|E|) (V = knopen, E = zijden), maar dat wordt ook nergens bewezen.

/mijn idee:
Je gaat namelijk de knopen af om kleuren te tellen, dat kost O(|V|), en vervolgens ga je alle zijden af om te kijken of de eindpunten van 1 zijde verschillend gekleurd zijn, dat kost O(|E|). Wat dus totaal O(|V|+|E|) kost, zodat hij inderdaad in polynomiale tijd te controlen is. Wat betekent dat 3COLOR (of hoe je het ook wilt noemen) NP compleet is.

Hoe lang het duurt om een certificaat te verifieren is totaal irrelevant, zolang het maar een polynomiale orde is. (Al geef ik een algoritme van orde O(|N E|^1000), dan is dat nog steeds polynomiaal en DUS zit het probleem in NP) Voor een NP membership bewijs is jouw verifier dus niet beter dan de mijne. Als je het echt moet implementeren ga je natuurlijk wel kijken naar de echte efficientie, maar dat is hier niet belangrijk, en daar heb ik me dus ook niet op geconcentreerd. Vervolgens zeg je: "Wat betekent dat 3COLOR (of hoe je het ook wilt noemen) NP compleet is." en dat is dus niet waar. Zie voor het verschil tussen NP en NP-compleet mijn eerste post. Een NP-Compleetheids bewijs is een stuk lastiger dan een NP membership bewijs. Ik ben bezig met een bewijsje voor de NP-compleetheid van 3COLOR, maar of ik dat helemaal afmaak hangt af van hoeveel tijd het me kost. (Het is voor mij namelijk al een tijdje geleden weet je. )

[Verwijderd]

Op vrijdag 15 februari 2002 19:01 schreef RickN het volgende:
De definitie van NP is niet wat door veel mensen wordt gedacht, nl. de problemen die niet in polynomiale tijd door een deterministische machine op te lossen zijn. Dit zou namelijk betekenen dat deze klasse van problemen disjunct is met de klasse P, de klasse van problemen die WEL in polynomiale tijd door een deterministische machine op te lossen zijn. Dat zou betekenen dat P <> NP en dat is nog helemaal niet bewezen (wel zeer waarschijnlijk overigens).

Ik weet niet helemaal meer welk voorbeeld van NP gebruikt werd, maar er was m.i. iig 1 voorbeeld waarvoor NP geldt, wat automatisch P != NP oplevert. (Ja hio 4 is wat weggezakt na 8 jaar ). Ik weet niet of het bepalen van de complete fractie van pi NP is, maar het lijkt me wel.

Overigens is het begrijp 'tijd' in deze definitie wel aardig: de definitie gaat er vanuit dat polynomiale tijd niet genoeg is voor probleem A, maar die tijd is afhankelijk van de stand van de techniek, tenzij het bewezen onmogelijk is (en dus oneindig veel tijd gaat kosten, ongeacht de stand van de techniek. (Travelling salesman probleem was vroeger NP dacht ik, nu niet meer.)

Hmm... dus er kan een tijd komen waarbij P == NP, puur omdat de stand van de techniek het begrip 'tijd' in een ander daglicht zet.

De goede definitie van de klasse NP is als volgt:
NP is de klasse van beslissings problemen die in polynomial tijd verifieerbaar zijn door een DFA.

En de problemen die niet in polynomial tijd verifieerbaar zijn door een DFA? Volgens mij zegt dit nl. niets over of een probleem NP is of niet. Het is wel zo dat bij problemen waar GEEN algoritme voor gevonden is, het uberhaupt lastig is om aan te tonen dat _wanneer_ er een algoritme wordt gevonden het NP is of niet.

[/quote]
Een equivalente definitie (ook aangestipt door mietje):
NP is de klasse vn beslissings problemen die in polynomiale tijd beslisbaar zijn door een NFA (Nondeterministic Finite Automata).
[/quote]

Volgens mij mocht je dat niet omdraaien.

Wat is dan verifieerbaarheid? Nou, dat is gegeven een oplossing bepalen of die oplossing ook echt een oplossing is.

Voorbeeldje: Het bepalen of een getal composiet is (d.w.z. factoren heeft) zit in de klasse NP. Niemand weet nog zeker of er een polynomiaal algoritme bestaat om dit te bepalen, maar het probleem is wel snel te verifieren, nl. als je mij een oplossing (deler) geeft, kan ik door een simele snelle deling bepalen of het ook echt een deler is.

Waarom is het wel verifieerbaar zijn van een oplossing de reden dat het NP is? Dit ontgaat me nl. volkomen. Polynomiale problemen zijn nl. ook soms te verifieren door een polynomiaal algoritme.

Wat is er leuk aan de klasse NP-compleet?
Als je een probleem in de klasse NP-compleet in polynomiale tijd kunt oplossen (op een DFA natuurlijk) dan kun je ELK probleem in NP in polynomiale tijd oplossen. Want elk probleem A in NP kan in polynomiale tijd worden omgeschreven tot een probleem B in NP-compleet. Polynomiale tijd voor het omschrijven van A naar B + polynomiale tijd voor het oplossen van B = polynomiale tijd in totaal voor het oplossen van A.

Nou, het zijn (of beter: het uitgaan van P != NP) van P != NP is de basis van de cryptografie: het CRYPTEN van een bak data met bekende sleutels zit in P, het DECRYPTEN van die bak data met onbekende sleutels zit in NP. (de z.g. one-way algoritmen: heen erg snel, terug onmogelijk op te lossen. 1 van die algoritmen is het berekenen van de coded-pincode, die op je pas staat. Die berekenen mbv de pincode is erg snel, de coded-pincode terugrekenen naar pincode is (nog) NP want inmens complex en ondoenlijk, ivm het one-way algoritme.

Wat moet je hiervan onthouden?

Nou, dat tijd het allemaal zal oplossen (letterlijk) -> bij voortschrijdende techniek is het begrip tijd in P != NP de beslissende factor wanneer een probleem P danwel NP is. Immers, je kunt niet volhouden dat een probleem NP is, als de stand der techniek aantoont dat het in polynomiale tijd kan .

[RickN]

Op maandag 18 februari 2002 20:45 schreef Otis een hele hoop iets.

edit:

In navolging van Otis zal ook ik mijn ego-trip post aanpassen

Suffice it to say dat in deze thread nu bij elkaar een redelijk introductie cursus complexiteits theorie staat

[Verwijderd]

Maar ff de stoffige shit uit 1993 doorgelezen. Het blijkt, zoals zovaak, een misverstand en wel een van mijn kant: ik veronderstelde dat NP de verzameling problemen zijn die niet in polynomiale tijd is op te lossen door een DFA, echter het is de verzameling problemen die in polynomiale tijd kan worden gechecked, maar waarvoor geen polynomiale tijd-algo voor bestaat. (dus P is deelverzameling van NP, maar NP is geen deelverzameling van P, althans, dat is niet bewezen). Ik heb de FI-rant maar weggehaald

voor de liefhebbers heb ik nog even gegoogled:
http://www.claymath.org/prizeproblems/pvsnp.htm
http://www.busygin.dp.ua/npc.html

en zo zijn er nog wel een paar duizend links.

[grasmaaier-FI over ego's van NP-grootte deleted]

(voor de goede orde, dit zei RickN hierboven ook al, maar hetgeen geschetst leek me zo onwaarschijnlijk, maar dat bleek wel degelijk waarheid).

[Verwijderd]

Ik weet niet of ik hiervoor een nieuwe post moet openen, of dat ik gewoon hieronder kan posten, maar ik zit met zo'n zelfde probleem, en ik kom er echt niet uit .

Het gaat om een gerichte, acyclische graaf G = (V,E), met I deelverzameling van V als de verzameling van alle knopen zonder inkomende takken en O deelverzameling van alle knopen zonder uitgaande takken, als mede een positief getal K.

Bestaat er een "diagnose"-verzameling met K of minder elementen waarmee elke enkelvoudige fout in G kan worden ontdekt? Met andere woorden, bestaat er een verzameling D deelverzameling van I x O met |D| <= K die voor elke v element V een paar i,o) element van D bevat met als eigenschap dat er ee gericht pad van i naar o via v is?

Het enige wat ik weet is dat ik uit moet gaan van het EXACT COVER BY 3-SETS-probleem.

[RickN]

En je moet hiervan NP-Compleetheid aantonen? Of alleen NP-membership?

Anyway, ik zal er es overnadenken.

Vertel ook ff wat dat EXACT-bladiebla probleem is. Mag je ervan uitgaan dat dat probleem NP-compleet is?

[Verwijderd]

Sorry, ik was het weekend niet echt online, problemen met mijn modem.

Ik moet echt bewijzen dat het probleem NP-Compleet is. NP-membership wordt al geimplicieerd doordat ik uit moet gaan van het EXACT-blabla probleem, waarvan ik mag uitgaan dat het NP-compleet is.

Het EXACT COVER BY 3-SETS-probleem (X3C):

INSTANCE: A finite set X where the size of X is divisible by 3, and a collection C of 3-element subsets of X.

QUESTION: Does C contain an exact cover for X, that is, a sub-collection C' such that every element of X occurs in exactly one member of C' ?

[RickN]

Ik vond het wel een leuk probleem, dus ik heb geprobeerd er een bewijs voor te schrijven. Ik heb nu iets dat in ieder geval al een eind in de buurt komt. Kijk maar of je er nog gaten in kunt schieten.

Het bewijs is denk ik nog niet helemaal goed, omdat volgens jouw beschrijving van het probleem ELK element in V op een pad moet liggen dat door een element in D wordt gerepresenteerd. Omdat I een deelverzameling is van V geldt dit dus ook voor alle elementen van I. In mijn bewijs is het van cruciaal belang dat NIET elke element in I wordt bereikt door een pad in D. (De elementen in I die wel door een pad in D worden bereikt bepalen namelijk de elementen uit C die in C' moeten worden opgenomen.)

bewijs in WORD formaat

[Verwijderd]

HEEL erg bedankt voor al de moeite die je er in gestoken hebt.

Het is inderdaad zo dat elke v uit V, dus ook de elementen i uit I op een pad moeten liggen.

Een probleem wat er volgens mij is, is om van X3C naar MS18 (of diagnose zoals jij het noemt) te gaan.


1 -> 2 -> 3 -> 4

Is een gerichte graaf, met 4 knopen (1 t/m 4) en 3 zijden. I = {1}, O = {4}. Er bestaat een deelverzameling van I x O, nl D = {1,4} waarvoor voor iedere v een pad bestaat van i naar o, via v. Namelijk voor alle vier het pad van 1 naar 4, via 2 en 3.

Nu wil ik dit probleem omzetten in X3C. Hoe ik dit precies moet aanpakken zie ik even niet.

[RickN]

Op dinsdag 26 februari 2002 16:07 schreef Esther het volgende:
[..]
Nu wil ik dit probleem omzetten in X3C. Hoe ik dit precies moet aanpakken zie ik even niet.

Waarom wil je dat? Voor het bewijzen van NP-compleetheid van MS18 moet je X3C omzetten in MS18, niet andersom.

Als ook elk element in I en O op een pad moet liggen betekend dat dus dat D tenminste MAX(|I|,|O|) elementen moet bevatten. Toch? En dus moet k ook tenminste zo groot zijn.

edit:
Ik heb nu een verbetering voor het bewijs in m'n hoofd. Ik hoop vanavond tijd te vinden om het goed op papier te krijgen.

[Verwijderd]

Hier wordt ons geleerd dat je allebei de kanten op moet kunnen met je reductie, zodat iedere oplossing van MS18 een oplossing is voor X3C en omgekeerd...

[RickN]

Eureka zal ik maar zeggen. Ik heb nu een bewijs waar (hopelijk ) echt geen speld meer tussen is te krijgen

herzien bewijs

Hiermee is het bewijs voor de NP-compleetheid van MS18 geleverd. Waarom jullie ook nog een reductie van MS18 naar X3C moeten leveren is me onduidelijk. Het is een leuke oefening, maar is niet nodig voor het bewijs. Dat MS18 naar X3C reduceert volgt namelijk triviaal uit het gegeven feit dat X3C NP-compleet is (en de aanname dat MS18 in NP zit).

Die reductie laat ik dus ook aan jou over . Ik hoop in ieder geval dat je iets hebt aan deze (wel zinvolle) reductie van X3C naar MS18.

B.T.W. was dit huiswerk? Best pittig dan. Wat voor opleiding doe je?

[Verwijderd]

Ik ben nog steeds bezig met de reductie van MS18 naar X3C, eigenlijk een beetje zinloos, want ik doe eigenlijk hbo, maar dacht erover om daarna naar de universiteit te gaan, maar ik denk dat dat een beetje te hoog gegrepen is voor me . Heel erg bedankt voor alle moeite die je erin gestoken hebt!