Etikett: np

Artiklar som i IDG:s ordlista handlar om den matematiska kategorin NP samt om P och NP-fullständig.

kappsäcksproblemet

(the knapsack problem) – att packa en kappsäck med ett urval föremål ur ett större antal så att kapp­säcken blir full, eller så full som möjligt. Före­målen är olika stora, och alla får inte plats. – Ett enkelt exempel är att kappsäcken har volymen 5 och föremålen har storlekarna 1, 2, 3, och 4. I så fall går det med 1+4 och 2+3. Det är enkelt, men om kappsäcken är större och föremålen många kan problemet bli omöjligt att lösa inom rimlig tid (ohanterligt). Det blir för många möjligheter att pröva. – Kapp­säcks­pro­blemet räknas som ett NP‑fullständigt problem. Det är ett opti­me­rings­pro­blem som har praktisk tillämpning inom områden som transport.

[matematik och logik] [ändrad 2 maj 2017]

Hamiltons problem

att i ett nät av noder och förbindelser mellan noderna hitta en väg som går genom varje nod exakt en gång och slutar i utgångspunkten. – Noderna och förbindelserna kan till exempel motsvara städer och vägar. Det spelar ingen roll hur lång vägen är. Om man hittar en väg som leder tillbaka till utgångspunkten kallas den för en Hamiltonsk cykel. Hamiltons problem räknas till de NP-fullständiga problemen. – Jämför med handelsresandeproblemet. – På engelska: the Hamiltonian path problem eller the Hamiltonian cycle problem. Uppkallad efter den irländska matematikern William Rowan Hamilton (1805—1865), se Wikipedia.

[matematik och logik] [ändrad 2 december 2019]

P

  1. – en klass av matematiska problem som det går relativt snabbt att lösa och snabbt att kontrollräkna. P står för polynom. – När det gäller matematisk komplexitet talar man om klasserna P, NP och de NP‑fullständiga problemen. P är den mest hanterliga klassen. Vanliga be­räk­ningar inom ekonomi och administration kan ses som problem i klassen P. – Att problemen går snabbt att lösa betyder att beräkningarna tar kort tid i förhållande till, grovt räknat, antalet tecken i den mate­mat­iska beskrivningen av problemet som ska lösas. För­kort­ningen P för polynom (eng­el­ska polynomial) syftar på att den maximala tidsåtgången för lösning av problemet kan uppskattas med en matematisk formel (ett polynom) med ledning av problemets algoritm. – Det finns tal i klassen P som det skulle ta hur lång tid som helst att lösa, men det är i så fall uppenbart på för­hand, även för en icke-matematiker. – När problemet väl är löst är det enkelt att kontrollera ifall lösningen är rätt. – Läs också om frågan om ifall P=NP?;
  2. – (för wait) – se semafor.

[förkortningar på P] [matematik och logik] [programmering] [ändrad 5 juni 2017]

handelsresandeproblemet

Hitta kortaste rutten som passerar alla punkterna.
Hitta kortaste rutten som passerar alla punkterna.

(traveling salesman problem) – ett klassiskt matematiskt problem som kan verka enkelt, men som kan vara mycket besvärligt att lösa. – En handelsresande ska be­söka ett antal städer. Avstånden mellan städerna är kända. Vilken är då den kortaste res­väg han kan välja om han ska be­söka varje stad och åter­vända till utgångspunkten? (Det finns varianter, beroende på om man får resa genom varje stad fler än en gång, eller bara en gång.) – I vissa fall är lösningen uppenbar, till exempel om städerna ligger i rät linje. Men en metod för lösning måste kunna tillämpas på alla tänkbara grupper av städer. – Redan när problemet gäller tio städer finns det över 3,6 miljoner tänkbara rutter (och det är bortsett från att man kan passera samma stad flera gånger). Ökar man antalet städer ytterligare blir problemet snart ohanterligt. Det tillhör därför den grupp av matematiska problem som kallas för NP‑fullständiga. – Det gäller också att bevisa att man verkligen har funnit den kortaste vägen. Och det finns ingen känd metod för att bevisa att man verkligen har funnit den kortaste vägen, förutom att gå igenom alla tänkbara lösningar och jämföra dem. Det är det som gör att handelsresandeproblemet räknas som NP‑full­ständigt. – Det mest omfattande handelsresandeproblem som hittills har lösts gäller 24 978 orter i Sverige: kortaste vägen om man vill besöka alla är 72 500 kilometer. – Problemet har praktisk tillämpning, till exempel inom trafikplanering och när man konstruerar elektroniska kretsar. Men i praktisk verk­sam­het brukar man inte behöva bevisa att man har hittat den absolut kortaste vägen: det räcker med en lösning som är bättre än alla tidigare. (Det finns fusklösningar som ofta ger tillräckligt bra, men inte perfekt, resultat. En enkel fusklösning är att alltid resa till närmaste obesökta stad på listan.) – En nära släkting till handelsresande­­problemet är Hamiltons problem. – Se Wikipedia.

[matematik] [transport och logistik] [ändrad 28 februari 2022]

NP-fullständig

(NP complete) – NP‑fullständiga problem eller NP‑kompletta problem – en klass av matematiska problem som är tidskrävande att lösa och också tidskrävande att verifiera (att be­visa att lösningen är rätt). – NP‑fullständiga problem är den mest ohanterliga typen av matematiska problem. Det mest kända exemplet är handelsresandeproblemet. – Typiskt för NP‑fullständiga problem är:

  • – att det inte finns något sätt – ingen algoritm – att hitta den bästa lösningen, förutom en uttömmande sökning;
  • – att det inte går att bevisa att man har funnit den bästa lösningen, utom genom att jämföra alla tänkbara lösningar.

– Andra, enklare klasser av matematiska problem är P och NP. – Se också komplexitet. – Välkända NP‑fullständiga problem gäller att hitta den kortaste vägen (handelsresandeproblemet, Hamiltons problem) eller att utnyttja ett utrymme så effektivt som möjligt (kappsäcksproblemet). Metoder för att lösa NP‑fullständiga problem har praktisk tillämpning, till exempel vid kretskonstruktion, transporter och kommunikation. I prak­tisk tillämpning räcker det ofta med att hitta en tillräckligt bra lösning, inte nödvändigtvis den bevisat bästa. – Utom i enkla fall är det mycket tidskrävande att lösa NP‑fullständ­iga program. Problem av denna typ blir snabbt ohanterliga, till exempel om man ökar antalet städer i handelsresandeproblemet till några tiotal. Det är lätt att formulera NP‑fullständiga problem som det skulle ta tusentals år att lösa med dagens snabbaste datorer. – NP‑fullständiga tal är en speciell typ av tal i NP‑klassen. Ingen har hittills funnit ett sätt att lösa NP‑fullständiga problem förutom genom en uttömmande prövning av alla tänkbara lösningar. Å andra sidan har ingen heller kunnat bevisa att en sådan algoritm inte kan finnas. (Se P=NP?.) – Matema­tiker diskuterar ifall de NP‑fullständiga problemen är en sort för sig, eller bara en typ av NP‑problem som vi ännu inte har kommit på hur man löser. Däremot har det bevisats att om någon hittar en algoritm som löser ett NP‑fullständigt problem så kan man med samma algoritm lösa alla andra NP‑fullständiga problem.

[matematik och logik] [ändrad 2 maj 2017]

P=NP?

i matematik: frågan om ifall alla matematiska problem i den besvärliga klassen NP i själva verket hör till den mer lätthanterliga klassen P. I så fall måste det finnas ett relativt enkelt sätt att lösa matematiska problem i klassen NP – fast hur det ska gå till har ingen kommit på än. De flesta matematiker anser att hypo­tesen P=NP? är fel, men det har inte be­vis­ats. – 2010 pre­senterade Vinay Deolalikar, då forskare på dåvarande Hewlett‑Packard†, ett påstått bevis för att hypotesen P=NP? är fel (alltså att P≠NP – se denna länk.) Men Deo­la­li­kars påstådda bevis har mött hård kritik. – Se Wiki­pedia och artikel i MIT News (länk).

[matematik] [ändrad 8 oktober 2020]

NP

en klass av matematiska problem som kan vara svåra att lösa, men som har lösningar som det är lätt att kontrollera. – När det gäller matematisk komplexitet talar man om de tre klasserna P, NP och de NP‑fullständiga problemen. – Klassen NP omfattar också klassen P, som består av de mest hanterliga pro­blemen, men oftast menar man med NP bara de problem som inte också ingår i P. (Se också frågan om ifall P=NP.) – När man säger att lösningarna går snabbt att kontrollera menar man i relation till problemets svårighetsgrad. Ett enkelt sätt att jämföra svårighetsgraden i olika problem är att räkna hur många tecken som ingår i det matematiska uttryck som beskriver problemet. – Ett exempel på NP‑problem är schemaläggning för gymnasium. Klasser, lärare och lektionssalar ska kombineras så att alla lektioner kan äga rum enligt läroplanen och ingen klass, lärare eller sal dubbelbokas. Det är besvärligt att sätta ihop ett schema, men lätt att kolla ifall det har blivit rätt. Ett annat exempel är att hitta primfaktorerna till mycket stora tal. Att hitta dem är svårt, att kontrollräkna är elementärt. När det däremot gäller problem i den NP‑fullständiga klassen så tar kontrollräkningen i princip lika lång tid som det tog att hitta lösningen. – NP står för non-deterministic polynomial. En förklaring till den benämningen står i i Wikipedia.

[förkortningar på N] [matematik] [ändrad 23 maj 2018]