Just nu i M3-nätverket
Jump to content

P och NP


CamillaS

Recommended Posts

Inte en simpel fråga att ge ett kort svar på, men om du inte alls berört det förut så handlar det enkelt uttryckt om en klassificering av problem och deras lösbarhet (dvs. om det existerar, eller kan existera, algoritmer för att lösa dem).

Men detta är en väldigt förenklad beskrivning och jag vet att just dessa begrepp gav mig schysst huvudvärk under algoritm- och komplexitetskurserna på högskolan.

 

 

Link to comment
Share on other sites

aa men jag har läst på lite om de. men väldigt lite.

jag har läst då att det som finns i NP finns även i P, kan det stämma?

för jag har en fråga där det antingen finns ett problem i P men inte i NP eller tvärtom men det måste väl då var i P men inte NP?

 

Link to comment
Share on other sites

jag har läst då att det som finns i NP finns även i P, kan det stämma?

Tvärtom, såvitt jag kommer ihåg. P är en delmängd av NP, så det som finns i P finns även i NP.

 

Däremot finns det i NP en mängd problem som faller under delmängden NP-kompletta, och denna delmängd är helt skild från P. Det sistnämnda gäller än så länge och det största teoretiska problemet som existerar inom detta teoriområde idag är att bevisa eller motbevisa detta.

 

* ett NP-problem är ett problem där en viss lösning kan kontrolleras enkelt via ett icke-deterministisk Turing-process.

* ett P-problem är samma sak, men verifieringen sker via en deterministisk process

* ett NP-Komplett problem är ett NP-problem där, om den givna lösningen är snabb, så är alla lösningar till problemet snabba. Med snabb betyder lösbar inom polynomisk tid.

 

Hur exakt lyder den fråga du fått förresten, du uttryckte det väldigt luddigt?

 

 

Link to comment
Share on other sites

så här lyder frågan exakt.

 

Avgör sanningshalten för följande påstående. Motivera ert svar:

• Det finns minst ett problem som tillhör P men inte NP.

• Det finns minst ett problem som tillhör NP men inte P.

 

om jag fattat de rätt så är det ju det sista som stämmer eller?

 

Link to comment
Share on other sites

Tja, du får ta mitt svar som ledsagan och inte sanning nu, eftersom det var ett par år sedan jag pluggade.

 

Första alternativet är fel, då P är en delmängd av NP. Motivering till varför så är fallet: Ett NP-problem kan verifieras med en icke-deterministisk Turingmaskin, men det kan även ett P-problem göras. Vid en icke-deterministisk verifiering kan ett givet vägval i Turing-maskinen påverkas av n utomstående faktorer. P-problemet är ett specialfall där n=0 och varje vägval enbart styrs av aktuellt tillstånd och aktuellt villkor.

 

Andra alternativet är korrekt, men jag är inte säker på motiveringen annat än att motsatsen skulle innebära att P=NP och detta har ju inte lyckats bevisas som sagt. Beviset för att det stämmer är att annars hade alla problem haft en deterministisk lösning och det finns gott om fall där detta motbevisats.

 

Nä, jag börjar bli osäker här, så du får det hela med en nypa salt och kombinera det med din kurslitteratur.

 

Link to comment
Share on other sites

Archived

This topic is now archived and is closed to further replies.



×
×
  • Create New...