CamillaS Postad 21 oktober, 2008 Share Postad 21 oktober, 2008 hej. jag sitter här funderar på vad P och NP är och deras skillnader. vore tacksam för lite hjälp. Länk till kommentar Dela på andra webbplatser More sharing options...
Anjuna Moon Postad 21 oktober, 2008 Share Postad 21 oktober, 2008 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. Länk till kommentar Dela på andra webbplatser More sharing options...
CamillaS Postad 21 oktober, 2008 Trådskapare Share Postad 21 oktober, 2008 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? Länk till kommentar Dela på andra webbplatser More sharing options...
Anjuna Moon Postad 21 oktober, 2008 Share Postad 21 oktober, 2008 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. Så * 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? Länk till kommentar Dela på andra webbplatser More sharing options...
CamillaS Postad 21 oktober, 2008 Trådskapare Share Postad 21 oktober, 2008 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? Länk till kommentar Dela på andra webbplatser More sharing options...
Anjuna Moon Postad 21 oktober, 2008 Share Postad 21 oktober, 2008 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. Länk till kommentar Dela på andra webbplatser More sharing options...
Cecilia Postad 21 oktober, 2008 Share Postad 21 oktober, 2008 Det finns en hel del artiklar på engelska Wikipedia, de rätar kanske ut en del frågetecken. http://en.wikipedia.org/wiki/Complexity_classes_P_and_NP Länk till kommentar Dela på andra webbplatser More sharing options...
Rekommendera Poster
Arkiverat
Det här ämnet är nu arkiverat och är stängt för ytterligare svar.