Beslutningsproblemer: Definition i beregneligheds- og kompleksitetsteori

Forstå beslutningsproblemer i beregneligheds- og kompleksitetsteori: definition, afgørlighed, ubesluttelighed og metodekrav for ja/nej-spørgsmål.

Inden for beregnelighedsteori og kompleksitetsteori er et beslutningsproblem et spørgsmål i et formelt system med et ja-eller-nej-svar. Svaret afhænger af værdierne af de indgående parametre. Beslutningsproblemer optræder typisk i matematiske spørgsmål om afgørelighed, dvs. spørgsmålet om eksistensen af en effektiv metode til at bestemme eksistensen af et objekt eller dets tilhørsforhold til en mængde. Nogle af de vigtigste problemer i matematikken er ubeslutbare.

Definition og formalisering

Formelt kan et beslutningsproblem ses som et sprog L over et alfabet Σ — altså en mængde af strengene over Σ. Et input x til problemet svarer til en streng, og beslutningsproblemet stiller spørgsmålet "x ∈ L?" Et algorithmisk svar til et beslutningsproblem er en Turing-maskine (eller anden beregningsmodel), der for ethvert input halter og accepterer hvis x ∈ L og afviser hvis x ∉ L. Hvis en sådan maskine findes, siger man, at problemet er beslutbart (eller rekursivt).

Beslutbarhed og uafgørlighed

• Beslutsom/decidable: Der findes en algoritme, der for hvert input i endelig tid giver korrekt ja/nej-svar.
• Semi-beslutsom / rekursivt opregnelig (RE): Der findes en algoritme, som accepterer alle ja-inputs, men som enten afviser eller aldrig stopper på nej-inputs. Sådanne sprog er ikke nødvendigvis decidable.
• Ubeslutbare problemer: Klassiske eksempler er stopningsproblemet (haltingproblemet) og flere problemer fra logik og teori om beregning, hvor ingen algoritme kan bestemme ja/nej for alle mulige input.

Kompleksitetsteori: tid, plads og klasser

I kompleksitetsteori ser man ikke kun på, om et problem kan løses, men hvor effektivt det kan løses. Væsentlige beslutningsproblemer grupperes i kompleksitetsklasser efter de ressourcer (tid, plads) som kræves af den bedste algoritme:

• P: problemer der kan løses i deterministisk polynomial tid.
• NP: problemer hvor ja-svar kan verificeres i deterministisk polynomial tid givet et passende bevis (eller hvor en ikke-deterministisk maskine beslutter problemet i polynomial tid).
• coNP: komplementet til NP.
• PSPACE, EXPTIME: andre almindeligt studerede klasser baseret på pladsforbrug eller eksponentiel tid.

Beslutningsproblemer er nyttige her, fordi man kan sammenligne og klassificere problemer ved at se på deres plads- og tidskompleksitet under standardkodninger af input.

Reduktioner og fuldstændighed

Et centralt redskab i analysen af beslutningsproblemer er reduktioner. En reduktion fra problem A til problem B viser, at A ikke er vanskeligere end B (givet en type reduktion):

• Mange-til-en (many-one) reduktion: En effektive funktion f omdanner ethvert input x til f(x) så x ∈ A ⇔ f(x) ∈ B. Polynomial tids many-one-reduktioner bruges f.eks. til at definere NP-fullstændighed.
• Turing-reduktioner: Tillader at løse A ved hjælp af et orakel for B og en effektiv procedure.

Et problem er fuldstændigt for en klasse (fx NP-komplet), hvis det ligger i klassen, og alle problemer i klassen kan reduceres til det. Fuldførelsesbegrebet hjælper med at identificere de "sværeste" problemer i en klasse.

Beslutningsproblem vs. søge- og optimeringsproblemer

Mange praktiske problemer præsenteres som søge- eller optimeringsproblemer. Man kan ofte formulere en beslutningsversion af et optimeringsproblem ved at spørge, om der findes en løsning med en værdi ≤ (eller ≥) en given grænse. Dette gør det muligt at anvende teorier om beslutningsproblemer til at klassificere optimeringsproblemer (fx SAT → valg af løsning, eller beslutningsversionen af 3-SAT).

Kodning af input og praktiske overvejelser

Et vigtigt teknisk punkt er, at et beslutningsproblems vanskelighed kan afhænge af, hvordan input er kodet (fx tal som binære vs. dekadiske repræsentationer). Når man taler om kompleksitetsklasser som P og NP, antager man altid en rimelig standardkodning af input for at undgå kunstige forskydninger i ressourcetrækket.

Eksempler

• SAT (satisfiability): Er en given boolesk formel tilfredsstilbar? — NP-komplet.
• Primality-testing: Er et givet tal primtal? — kendt at ligge i P.
• Stopningsproblemet: Giver en Turing-maskine halt på et givet input? — ubeslutbart.
• Medlemskabsproblemer for regulære og kontekstfrie sprog: typisk decidable via automater eller parseralgoritmer.

Afsluttende bemærkninger

Beslutningsproblemer udgør en central ramme i både beregneligheds- og kompleksitetsteori, fordi de tillader en klar formalisering af spørgsmål om hvad der kan beregnes, og hvor effektivt. Ved hjælp af begreber som decidability, rekursiv opregnelighed, kompleksitetsklasser og reduktioner får man et sprog til at sammenligne problemer, identificere vanskelige tilfælde og forstå begrænsningerne ved algoritmer. For mange praktiske problemer er analysen via beslutningsversionen afgørende for at bestemme om problemet er teoretisk løsbart, eller om man i stedet må søge tilnærmede eller heuristiske metoder.

Spørgsmål og svar

Q: Hvad er et beslutningsproblem?

Q: Inden for hvilke studieretninger optræder beslutningsproblemer?

Q: Hvad er betydningen af decidability?

Spørgsmål: Kan alle problemer i matematik afgøres?

Q: Hvad er et uafgørligt problem?

Q: Er svaret på et beslutningsproblem altid ja eller nej?

Q: Hvad afhænger svaret på et beslutningsproblem af?

Søg efter bogstav