College aantekeningen
CS3052 Computational Complexity FULL COURSE
- Vak
- Instelling
Personal revision notes
[Meer zien]Voorbeeld 4 van de 35 pagina's
Voorbeeld 4 van de 35 pagina's
In winkelwagen
In winkelwagen
gesponsord bericht van onze partner
Verkoper
Volgen
WinterBerry
Voorbeeld van de inhoud
CS3052 BibleNotes for CS3052: Computational Complexity
S2 - 2021/2022
Contents
1 Finite State Automata 3
1.1 Deterministic Finite State Automaton (DFA) . . . . . . . . . . . . . . . . . . . . . 3
1.2 Regular Language . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Non-deterministic Finite State Automaton (NFA) . . . . . . . . . . . . . . . . . . . 4
1.4 NFA to DFA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.5 Regular Expressions and Regular Languages . . . . . . . . . . . . . . . . . . . . . . 7
1.6 From RegEx to NFA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.7 From NFAs to RegEx . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.8 The Pumping Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2 Context-Free Languages and Pushdown Automata 10
2.1 Pushdown Automata (PDA) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2 Context-free languages (CFL) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3 CFG to PDA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.4 Pumping Lemma for CFL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3 Turing Machines (TM) 14
3.1 TM Configurations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.2 Turing Recognisable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.3 Variants of Turing Machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.4 Multitape TM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.5 Non-deterministic TM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.6 Certificate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4 Limits of Computation 17
4.1 Church-Turing Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.2 Turing-completeness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.3 Decidability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.3.1 Turing Decidable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.4 Acceptance Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.5 Halting Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.6 Property . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.6.1 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.7 Rice’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.8 Infinity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.9 Hierarchy of Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1
,5 Complexity 20
5.1 Running time/Time complexity/Complexity . . . . . . . . . . . . . . . . . . . . . . 20
5.2 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
5.3 Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
5.4 Complexity Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
5.5 Formal definitions of Poly and Expo . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
6 Recursive Algorithms 22
6.1 The Master Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
7 Non-deterministic Complexity Classes 23
7.1 Verifier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
7.2 Polytime Verifier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
7.3 PolyCheck . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
7.4 NPoly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
7.5 PolyCheck, NPoly, Expo, Poly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
8 Decision Problems 26
8.1 P vs NP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
8.2 Polyreductions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
8.3 NP-Completeness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
8.4 Polyequivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
8.4.1 UHC ≤P DHC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
8.4.2 DHC ≤P UHC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
8.5 NP-hard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
8.6 Formal Definitions of Satisfiability Problems . . . . . . . . . . . . . . . . . . . . . . 29
8.6.1 CircuitSAT ≤P SAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
8.6.2 SAT ≤P CircuitSAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
8.6.3 3-SAT ≤P SAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
8.6.4 SAT ≤P 3-SAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
8.7 CircuitSAT is NP-complete . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
8.7.1 Sketch of proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
8.8 Proof Techniques for NP-completeness . . . . . . . . . . . . . . . . . . . . . . . . . 31
9 Summary 32
9.1 Space Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
10 Amortised Complexity 35
2
,1 Finite State Automata
Definitions:
• Alphabet: finite set A of symbols
• Elements of A are letters.
• A word (or string) over A is a finite sequence of letters, written w = a1 a2 ...an , where each
ai ∈ A.
• The length of a word is n (the number of letters).
• The empty word is written as ε (has length 0 and consists of no letters).
• Concatenation is writing one word after another to make a longer word.
– Note: εw = wε = w
• A∗ denotes the set of all words over A and includes ε. A language is a subset of A∗ .
1.1 Deterministic Finite State Automaton (DFA)
A deterministic finite state automaton (DFA) M is a 5-tuple consisting of:
1. Alphabet A (a finite set).
2. Finite set of states, S.
3. Transition function F : A × S → S with input: (letter, state), output: (state).
4. A state s0 ∈ S called the initial or start state.
5. A subset T ⊆ S containing the accept states or terminals.
Write M = (A, S, F, s0 , T ), which starts in state s0 and reads a word w = a1 a2 ...an (where w ∈ A∗ )
one letter at a time from left to right.
If M is in state s ∈ S and reads letter a, then it moves to state F (a, s).
M accepts the word w if after reading letter an it is in an accept state t (t ∈ T ).
M rejects the word w if after reading letter an it is in a state S \ T (a reject state).
Example
M = (A = {a, b}, S = {s0 , s1 , s2 }, F, s0 , T = {s2 }) where F is the state-transition function described
below:
F s0 s1 s2
a s1 s1 s1
b s2 s2 s1
3
, 1.2 Regular Language
Let M = (A, S, F, s0 , T ) be a DFA. The language L(M ) defined by M (also say accepted by M ) is
the set of all words from A∗ which bring M from s0 into an accept state .
A language L is regular if there exists a DFA M with L = L(M ).
Lemma: If L is a finite language, then L is regular.
1.3 Non-deterministic Finite State Automaton (NFA)
A non-deterministic finite state automaton (NFA) is a 5-tuple (A, S, F, s0 , T ) where A, S, s0 and T
are the same as for a DFA (Section 1.1), but now F is a function from (A ∪ {ε}) × S to P(S). The
power set of S is the set of all subsets of S.
It is allowed for an NFA to have:
• F (a, s) = ∅ to be the empty set, so no arrows are leaving the state s when a is read.
• F (a, s) = {s′ , s′′ } so from state s there can be more than one state transition when a is read.
• F (ε, s) = s′ empty transitions that do not require the NFA to read any symbols to move.
An NFA N accepts a word w if there exists a directed path from s0 to an accept state whose labels
concatenate to give w (i.e. the letters of w appear in order but there may be one or more ε before
or after each letter).
The language L(N ) defined by N is the set of all words that N accepts.
Can think of an NFA as computing in parallel on the word w, where more than one branch of com-
putation is ”alive” at the same time. It accepts if any of the branches of computations accepts .
Example:
N = (A = {a, b}, S = {s0 , s1 , s2 , s3 , s4 }, F, s0 , T = {s4 })
4
Voordelen van het kopen van samenvattingen bij Stuvia op een rij:
Verzekerd van kwaliteit door reviews
Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!
Snel en makkelijk kopen
Je betaalt supersnel en eenmalig met iDeal, creditcard of Stuvia-tegoed voor de samenvatting. Zonder lidmaatschap.
Focus op de essentie
Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!
Veelgestelde vragen
Wat krijg ik als ik dit document koop?
Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.
Tevredenheidsgarantie: hoe werkt dat?
Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper WinterBerry. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €21,55. Je zit daarna nergens aan vast.
Is Stuvia te vertrouwen?
4,6 sterren op Google & Trustpilot (+1000 reviews)
Afgelopen 30 dagen zijn er 76799 samenvattingen verkocht
Opgericht in 2010, al 14 jaar dé plek om samenvattingen te kopen