Turing-machine: de grenzen van berekenbaarheid

[Electrowolf]

Helaas staan er wat onvolledigheden in het artikel en onduidelijkheden wat betreft P = NP (reviews: Turing-machine: de grenzen van berekenbaarheid).

Zo bevat P niet alleen de problemen die oplosbaar zijn polynomiale tijd maar ook de problemen die verifieerbaar zijn in polynomiale tijd. Problemen in NP zitten dus ook in P (athands, volgens de meeste mensen ).

Verder zou het voor buurvrouw Truus ook verhelderend zijn als er een voorbeeldje bij komt wat nou een probleem uit NP is. Makkelijke en mooie voorbeelden zijn TSP of de Hamiltonian cycle. Voor Hamiltonian cycle zou dit neerkomen op:

Gegeven een aantal steden met wegen er tussen, kan ik zo rijden dat ik alle steden een keer bezoek en weer eindig bij het begin?

Dit is verifieerbaar in polynomiale tijd door de route na te lopen (rijden) en te kijken of je alle steden hebt gehad. Het maken van deze route is helaas niet zo makkelijk, effectief moet je alle oplossingen proberen en dat zijn er best veel: n! (faculteit). Maar "gelukkig" kan dit tegenwoordig al in 2^n, maar dit is nog steeds erg langzaam.

Update:
Zie nu dat er op de volgende pagina een TSP voorbeeldje staat, dus misschien beetje dubbel op om ook HC te doen . Wel wordt het grote verschil tussen "geef de kortste", "geef een oplossing van maximaal x" en "is er een oplossing van maximaal x" subtiel genegeerd maar wel gebruikt in het voorbeeld.

edit:

Updateje, sneller lezen volgende keer >_>.

[ Voor 13% gewijzigd door Electrowolf op 23-06-2012 12:19 ]

[robvanwijk]

Op de laatste pagina staan twee dingen die echt niet kloppen:

De consequentie daarvan is dat er ook P-problemen zijn die oneindig veel polynomiale tijd kosten om op te lossen.

Nee, niet oneindig veel; absurd veel, onwerkbaar veel, 10^n keer de leeftijd van het heelal, ja dat wel, maar nooit "oneindig" veel (een polynoom waar de onafhankelijke waarde ("x") een eindig getal is, zal altijd een eindig getal als afhankelijke waarde ("resultaat", "y") opleveren).
Normaal gesproken zou ik de dichterlijke vrijheid negeren, maar in dit geval gaat het over de kern van het artikel.

Dat wil zeggen dat er een quantumalgoritme bestaat waarmee de priemfactoren van getallen efficiënt kunnen worden gevonden.

Ook dit is een subtiel maar belangrijk foutje; hoewel je in de praktijk best kunt zeggen dat iets "niet kan" puur omdat het miljarden jaren duurt, betekent nog niet dat het in theorie niet mogelijk is. En aangezien het hele artikel over berekenbaarheidstheorie gaat stel ik voor om hier een woordje toe te voegen.

@Electrowolf: ja dat subtiele "even onder het tapijt, jij eng detail" viel me ook al op. Ik denk echter dat het netjes uitleggen (vind een oplossing, ga dan (binary/linearly) searchen naar steeds betere totdat het niet meer lukt, de laatste oplossing die we hebben gevonden is de oplossing) wat ver afdwaalt van de essentie van het artikel (en voor de echt geïnteresseerden makkelijk genoeg zelf te vinden (of te bedenken) is).

[Olaf]

Ik zal de schrijver van het stuk op dit topic wijzen. Hij zal dan eventueel de nodige wijzigingen doorvoeren.

[z.jeroen]

Zo bevat P niet alleen de problemen die oplosbaar zijn polynomiale tijd maar ook de problemen die verifieerbaar zijn in polynomiale tijd. Problemen in NP zitten dus ook in P (athands, volgens de meeste mensen ).

Wat je zegt klopt echt niet. Problemen die verifieerbaar zijn in polynomiale tijd?

In de formele definitie van P gaat het over decision problems, problemen met een ja/nee-antwoord. Bijvoorbeeld: is x een priemgetal? Als je voor iedere invoer de vraag juist kan beantwoorden in polynomiale tijd, dan zit het probleem in P. That's it.

Wat bedoel jij met oplosbaar en verifieerbaar? Volgens mij ben je in de war. NP is de klasse van problemen waarvan het antwoord verifieerbaar is in polynomiale tijd.

NP zit in P? Nee, dat weten we niet.

[ Voor 6% gewijzigd door z.jeroen op 23-06-2012 23:36 ]

[Electrowolf]

Ik heb even de bijbel er bij gepakt; Introduction to Algorithms van Cormen et. al.

The class P consists of those problems that are solvable in polynomial time. More
specifically, they are problems that can be solved in time O(nk) for some constant k, where n
is the size of the input to the problem. Most of the problems examined in previous chapters
are in P.

The class NP consists of those problems that are "verifiable" in polynomial time. What we
mean here is that if we were somehow given a "certificate" of a solution, then we could verify
that the certificate is correct in time polynomial in the size of the input to the problem. For
example, in the hamiltonian-cycle problem, given a directed graph G = (V, E), a certificate
would be a sequence v1, v2, v3, ..., v|V| of |V| vertices. It is easy to check in polynomial time
that (vi, vi+1) E for i = 1, 2, 3, ..., |V| - 1 and that (v|V|, v1) E as well. As another example,
for 3-CNF satisfiability, a certificate would be an assignment of values to variables. We can
easily check in polynomial time that this assignment satisfies the boolean formula.

Je hebt dus gelijk dat verfieerbaarheid in polynomiale tijd betekend dat het in NP zit, niet in P. Maar dat betekend dus ook dat P in NP zit en dat, zoals je al zegt, NP in P de vraag is.

Was waarschijnlijk even in de war met de definitie van NP-compleet waar je vaak in twee stappen denkt: zit probleem in NP en kan ik het reduceren naar een ander NP-compleet probleem (of echt bewijzen...) en daardoor de verkeerde "stap omlaag" maakte.

Thanks .