Pseudo-polynomiaal algoritme

Moderators: jkien, Xilvo

Reageer
Berichten: 114

Pseudo-polynomiaal algoritme

Wat is precies de betekenis van een pseudo-polynomiaal algoritme ? Want de definitie en het voorbeeld op wikipedia maken me niet veel wijzer.

Gebruikersavatar
Berichten: 2.609

Re: Pseudo-polynomiaal algoritme

Wikipedia zegt dat het algoritme een polynomiale tijd heeft in functie van de waarde van de input. Bij gewone polynomiale algoritmen is de lengte van de input belangrijk, daar maakt het dan uit in welke codering (unair, binair) de input gegeven wordt. Dat is dus bij pseudo polynomiaal niet het geval.

Opmerking moderator

Dit past volgens mij beter in Programmeren, bij deze verplaatst.

Berichten: 114

Re: Pseudo-polynomiaal algoritme

Dus een gewoon polynomiaal of exponentieel algoritme drukt de tijd uit in functie van de inputgrootte.

1) Wilt dit dan zeggen dat men een andere tijdscomplexiteit krijgt afhankelijk van je codering ? Betekent dit dan wanneer je voor een probleem een algoritme vind dat polynomiaal is als je het in decimale getallen uitdrukt, het algoritme mogelijk niet meer polynomiaal zal zijn wanneer je het in binaire getallen uitdrukt ?

Bij een pseudo-polynomiaal algoritme zeg je dat de tijdscomplexiteit wordt uitgedrukt in functie van de inputwaarde en dat een pseudo-polynomiaal algoritme ook geen verschillende tijdscomplexiteit zal opleveren wanneer men een ander getallenstelsel gebruikt.

Dit begrijp ik niet helemaal, want:

2) Moet de tijdscomplexiteit niet altijd worden uitgedrukt in functie van de inputgrootte ?

Als je bijvoorbeeld het Ford Fulkerson-algoritme neemt dat pseudo-polynomiaal is, dan bekom je volgende tijdscomplexiteit O [ (sommatie van de waarde van alle arcs) * aantal arcs ] als je het in functie van de inputwaarde uitdrukt.

Als je dit algoritme in functie van de inputgrootte uitdrukt en je veronderstelt:

- |A| = aantal arcs ;

- Alle arcs hebben een capaciteit van 2^|A|, een instantie kan dus gecodeerd worden door |A| integers elk van |A| bits lang.

De tijdscomplexiteit wordt dan O (2|A|* |A|²).

Wat ik hiervan niet begrijp, is:

3) Een inputwaarde moet toch ook uitgedrukt worden in een bepaalde codering, bijgevolg zal wanneer je voor een bepaalde codering kiest de tijdscomplexiteit van het algoritme toch ook veranderen naargelang de codering ? Is dit ook niet in het voorbeeld zo, want men lijkt eerst een polynomiale tijdscomplexiteit te hebben, maar wanneer men voor een binaire codering kiest, krijgt men een exponentiële tijdscomplexiteit.




Gebruikersavatar
Berichten: 2.609

Re: Pseudo-polynomiaal algoritme

Ik moet bekennen dat ik er tot voor dit topic nog nooit van gehoord had. Ik vind het ook niet terug in het referentiewerk dat mijn prof Berekenbaarheid/Complexiteit gebruikte (Sipser 2006). En hoe meer ik ernaar kijk, hoe vreemder ik het zelf ook begin te vinden. Op internet is er ook niet al te veel over te vinden.

Er stond wel nog een subtiel stukje tussen haakjes op wikipedia: "if its running time is polynomial in the numeric value of the input (which is exponential in the length of the input – its number of digits)"

En verder: "The distinction between the value of a number and its length is one of encoding: if numeric inputs are always encoded in unary, then pseudo-polynomial would coincide with polynomial.".

Ik vermoed dat er in deze klasse dus standaard uitgegaan wordt van binaire codering, anders valt het gewoon in de klasse P.

Het voorbeeld dat daar gegeven wordt (priemtest) redeneert enkel op basis van de grootte van het getal, je ziet nergens onderstellingen over de codering.

Hier lees ik ook dat “A pseudo-polynomial-time algorithm … will display 'exponential behavior' only when confronted with instances containing 'exponentially large' numbers, [which] might be rare for the application we are interested in. If so, this type of algorithm might serve our purposes almost as well as a polynomial time algorithm.”.

Reageer