Hvilke grundlæggende matematiske definitioner, notationer og introduktioner er nødvendige for at forstå formalismen i beregningskompleksitetsteorien?

by EITCA Academy / Søndag, 11 May 2025 / Udgivet i Cybersecurity, EITC/IS/CCTF Computational Complexity Theory Fundamentals, Introduktion, Teoretisk introduktion

Beregningskompleksitetsteori er et grundlæggende område inden for teoretisk datalogi, der grundigt undersøger de ressourcer, der kræves for at løse beregningsproblemer. En præcis forståelse af dens formalisme kræver kendskab til adskillige centrale matematiske definitioner, notationer og konceptuelle rammer. Disse giver det sprog og de værktøjer, der er nødvendige for at formulere, analysere og sammenligne problemers beregningsmæssige sværhedsgrad og algoritmers effektivitet.

1. Mængder, funktioner og relationer

sæt

En mængde er en veldefineret samling af forskellige objekter, kaldet elementer. I kompleksitetsteori repræsenterer mængder ofte samlinger af strenge, tal eller tilstande. Standardnotationen for en mængde er store bogstaver, såsom $S$ or $A$ . For eksempel, $\Sigma$ betegner almindeligvis et alfabet - et endeligt sæt af symboler.

- Eksempel: If $\Sigma = \{0, 1\}$ , så er mængden af alle binære strenge med længde 3 $\Sigma^3 = \{000, 001, 010, 011, 100, 101, 110, 111\}$ .

Funktioner

En funktion $f: A \til B$ tildeler til hvert element $en \i A$ præcis ét element $b \i B$ Funktioner er grundlæggende for at beskrive algoritmer, transformationer og kompleksitetsmål.

- Eksempel: funktionen $f(n) = 2^n$ afbilder naturlige tal til deres respektive potenser af to.

forbindelser

En relation $R \subseteq A \times B$ er en delmængde af det kartesiske produkt af mængder $A$ og $B$ I forbindelse med sprog og beslutningsproblemer beskriver relationer ofte kortlægningen mellem input og deres tilhørende output eller certifikater.

2. Alfabeter, strenge og sprog

Alfabet og strenge

Et alfabet $\Sigma$ er et endeligt, ikke-tomt sæt af symboler. En streng over $\Sigma$ er en endelig sekvens af symboler fra $\Sigma$ Sættet af alle strenge over $\Sigma$ er betegnet $\Sigma^*$ Hvor $*$ repræsenterer Kleene-stjerneoperationen.

- Eksempel: Til $\Sigma = \{a, b\}$ , $abbab$ er en streng i $\Sigma^*$ .

Other languages

Et sprog $L$ i løbet af $\Sigma$ er en hvilken som helst delmængde af $\Sigma^*$ I beregningskompleksitet repræsenterer sprog beslutningsproblemer: for en streng $x \in \Sigma^*$ , spørgsmålet er, om $x \in L$ .

- Eksempel: Sproget $L = \{w \in \{0,1\}^* : w$ indeholder et lige antal nuller $\}$ .

3. Beslutningsproblemer og beregningsmodeller

Beslutningsproblemer

Et beslutningsproblem stiller et ja/nej-spørgsmål om et input. Formelt set svarer det til et sprog $L ≥ 100°C (≥ 100°F)$ : "Givet $x$ , er $x \in L$ ? "

- Eksempel: "Givet en graf $G$ , gør $G$ har en Hamilton-cyklus?" er et beslutningsproblem.

Beregningsmodeller

Kompleksitetsteori formaliserer beregning ved hjælp af abstrakte maskiner. Den mest fremtrædende er Turingmaskinen.

- Turing-maskinen (TM): En abstrakt model defineret af et endeligt sæt af tilstande, et uendeligt bånd opdelt i celler, et båndhoved og en overgangsfunktion. En deterministisk Turing-maskine (DTM) har en enkelt overgang for hvert tilstandssymbolpar; en ikke-deterministisk Turing-maskine (NTM) kan have flere overgange.

4. Asymptotisk notation

Asymptotisk notation beskriver funktioners begrænsende adfærd, som er vigtig for at udtrykke ressourceforbruget (tid, rum) af algoritmer, når inputstørrelsen vokser.

Stor O-notation

- Definition: $f(n) = O(g(n))$ hvis der findes konstanter $c > 0$ og $n_0$ sådan at for alle $n ≥ n₀$ , $|f(n)|≤ c ≥ |g(n)|$ .
- fortolkning: $f(n)$ vokser ikke hurtigere end $g(n)$ op til konstante multipler for store $n$ .

- Eksempel: $3n^2 + 2n + 1 = O(n^2)$ .

Omega- og Theta-notationer

- Stor Omega ( $\Omega$ ): $f(n) = Ω(g(n))$ hvis for nogle $c, n_0$ , $f(n) ≤ c ≥ g(n)$ for alle $n ≥ n₀$ .
- Stor Theta ( $\Theta$ ): $f(n) = ∫Theta(g(n))$ if $f(n) = O(g(n))$ og $f(n) = Ω(g(n))$ .

Disse notationer muliggør formel sammenligning af algoritmisk effektivitet.

5. Kompleksitetsmål

Tidskompleksitet

Beskriver antallet af beregningstrin (f.eks. overgange i en Turing-maskine), der kræves som funktion af inputstørrelsen. $n$ .

- Bedømmelse: $T(n)$ or $f(n)$ for tid taget på input af længde $n$ .

Rumkompleksitet

Beskriver mængden af hukommelse (brugte båndceller) som en funktion af inputstørrelse.

- Bedømmelse: $S(n)$ .

Ressourcegrænserne betragtes typisk i asymptotisk forstand for store inputstørrelser.

6. Kompleksitetsklasser

Kompleksitetklasser grupperer sprog (problemer) i henhold til de ressourcer, der er nødvendige for at afgøre dem.

P (Polynomisk tid)

- Definition: Den klasse af sprog, der kan afgøres af en deterministisk Turing-maskine i polynomisk tid.
- Formalisering: $P = \bigcup_{k \geq 1} \mathrm{DTIME}(n^k)$ .
- Eksempel: Sortering af en liste, kontrol af om et tal er et primtal.

NP (ikke-deterministisk polynomisk tid)

- Definition: Den klasse af sprog, for hvilke en løsning kan verificeres i polynomisk tid af en deterministisk Turing-maskine, eller tilsvarende, bestemmes af en ikke-deterministisk Turing-maskine i polynomisk tid.
- Formalisering: $NP = \bigcup_{k \geq 1} \mathrm{NTIME}(n^k)$ .
- Eksempel: Opfyldelighed (SAT), Hamiltonsk cyklus.

Andre klasser

- PSPACE: Sprog, der kan afgøres i polynomiumsrum.
- UDLØBSTID: Sprog, der kan afgøres i eksponentiel tid.

7. Nedsættelser

Reduktioner er kortlægninger fra ét problem til et andet, der demonstrerer relativ beregningsmæssig vanskelighed.

Mange-en-reduktion ( $\leq_m$ )

Et sprog $A$ er mange-en reducerelig til $B$ ( $A ≤ B$ ) hvis der findes en beregningsbar funktion $f$ sådan at $x i A og f(x) i B$ .

- Formål: If $B$ er let, og $A ≤ B$ , derefter $A$ er højst lige så svært som $B$ .

Polynomiel tidsreduktion ( $\leq_p$ )

En polynomialtidsberegnelig reduktion bruges til at sammenligne problemer inden for $P$ og $NP$ . hvis $f$ kan beregnes i polynomisk tid, og $x i A og f(x) i B$ , derefter $A ≤ B$ .

8. NP-Fuldstændighed

Et problem er NP-komplet hvis:
1. Det er i $NP$ .
2. Ethvert problem i $NP$ er polynomiel tid reducerelig til den.

Bedømmelse: $L$ er NP-fuldstændig hvis $L \i NP$ og $\forall L' \in NP, L' \leq_p L$ .

- Eksempel: SAT-problemet er det kanoniske NP-komplette problem.

9. Beslutnings- vs. søgeproblemer

Mens beslutningsproblemer stiller ja/nej-spørgsmål, kræver søgeproblemer at finde en eksplicit løsning. Kompleksitetsteori fokuserer ofte på beslutningsproblemer, men søgeproblemer er tæt beslægtede, især inden for kryptografi og algoritmedesign.

10. Formel sprogteori

Kompleksitetsteori udnytter formel sprogteori til at repræsentere og analysere problemer.

- Almindelige sprog: Genkendt af endelige automater.
- Kontekstfrie sprog: Genkendt af pushdown-automater.
- Rekursive (afgørbare) og rekursivt optællelige (semi-afgørbare) sprog: Anerkendt af Turing-maskiner med eller uden stopgarantier.

11. Notation for Turingmaskiner

En Turing-maskine $M$ er specificeret af en tuple $(Q, ≥Sigma, ≥G, ≥Δ, q₀, q₀a, q₀r)$ , hvor:

- $Q$ Endelig sæt af tilstande
- $\Sigma$ Indtast alfabet (inkluderer ikke blankt symbol)
- $\Gamma$ Båndalfabet ( $Sigma = Gamma$ ), inkluderer et blankt symbol
- $\delta$ Overgangsfunktion
- $q_0$ Starttilstand
- $q_a$ Accepter stat
- $q_r$ Afvis tilstand

Beregningen af $M$ på input $w$ er betegnet $M(k)$ .

12. Inputstørrelse

Længden af inputtet, betegnet $n$ , måles som $| X |$ , antallet af symboler i inputstrengen $x$ Alle kompleksitetsmål (tid, rum) udtrykkes som funktioner af $n$ .

13. Universel Turingmaskine

En universel Turing-maskine $U$ kan simulere enhver Turing-maskine $M$ på input $w$ , givet en beskrivelse $\langle M \rangle$ og $w$ Dette danner det teoretiske grundlag for Church-Turing-tesen.

14. Certifikater og verifikatorer

Til $NP$ problemer, en verifikator er en deterministisk Turing-maskine $V$ således at for ethvert input $x$ , der findes et certifikat $y$ (med $|y|$ polynomium i $| X |$ ) tilfredsstillende $V(x, y) = 1$ hvis og kun hvis $x$ er et "ja"-eksempel.

- Eksempel: For SAT er certifikatet en tilfredsstillende opgave.

15. Randomiserede kompleksitetsklasser

- RP (Randomiseret polynomiel tid): Problemer, hvor en probabilistisk Turing-maskine kan bestemme medlemskab med ensidig fejl i polynomisk tid.
- BPP (Bounded-fejl Probabilistic Polynomial Time): Problemer, hvor en probabilistisk Turing-maskine kan bestemme medlemskab med tosidet fejl i polynomisk tid.

16. Oracle-maskiner

En orakel-Turingmaskine har adgang til et "orakel", der øjeblikkeligt beslutter medlemskab i et fast sprog $A$ Dette koncept bruges til at studere relativ beregnelighed og adskillelser mellem klasser.

17. Hierarki-teoremer

Hierarkiteoremer formaliserer ideen om, at flere ressourcer muliggør løsningen af flere problemer.

- Tidshierarki-sætning: Der findes problemer, der kan løses på længere tid, men ikke kortere.
- Rumhierarki-sætning: Analog udsagn for rum.

18. Fuldstændighed og hårdhed

- Hårdhed: Et problem $L$ is $C$ -svært hvis alle problemer i klassen $C$ reducerer til $L$ .
- Fuldstændighed: $L$ is $C$ -fuldfør hvis $L \i C$ og $L$ is $C$ -hård.

19. Boolske kredsløb

Boolske kredsløb modellerer beregning som acykliske netværk af logiske gates. Kredsløbskompleksitet studerer størrelsen (antal gates) og dybden (niveauer af gates), der er nødvendige for at beregne funktioner.

20. Kodning og repræsentation

Alle objekter (Turing-maskiner, grafer, formler) skal kodes som strenge over et endeligt alfabet for at kunne analyseres inden for kompleksitetsteori. Standardkodninger sikrer ensartet behandling og sammenlignelighed af problemer og algoritmer.

—

Beherskelse af disse definitioner og formelle notationer er nødvendig for en præcis og grundig forståelse af beregningskompleksitetsteori. Disse formelle værktøjer understøtter klassificeringen af beregningsproblemer, design og analyse af algoritmer og studiet af kryptografiske sikkerhedsantagelser.

Andre seneste spørgsmål og svar vedr EITC/IS/CCTF Computational Complexity Theory Fundamentals:

Se flere spørgsmål og svar i EITC/IS/CCTF Computational Complexity Theory Fundamentals

Flere spørgsmål og svar:

Mark: Cybersecurity
program: EITC/IS/CCTF Computational Complexity Theory Fundamentals (gå til certificeringsprogrammet)
Lektie: Introduktion (gå til relateret lektion)
Emne: Teoretisk introduktion (gå til relateret emne)

Tagged under: Kompleksitetsklasser, Cybersecurity, Formelle sprog, Matematik, NP-fuldstændighed, Turing-maskiner

EITCA Academy

LOG IND PÅ DIN KONTO

Glemt din adgangskode?

OPRET EN KONTO