complexity Flashcards
(114 cards)
1
Q
How do you convert a regex to an NFA?
A
- Create an NFA for each regex component (concatenation, union, and Kleene star).
- Combine components following regex rules.
- Use epsilon transitions to join smaller NFAs into a complete structure.
studres ver:
Let N = (Q, Σ, δ, q0, F) be an NFA. We replace states and letters with regular expressions as
follows:
1. Add a new start state s, connected to q0 by an ε-arrow
2. Add a new accept state t, with an ε-arrow from each accept state to t. Set F = {t}, so t is the only accept state
3. “Rip out” one state at a time until only s and t remain, replacing arrows to and from that state with appropriate regular expressions
The process will terminate with just states s and t, with an arrow between them labelled with a regular expression R. This regular expression describes L(N).
2
Q
How do you construct a PDA that recognises a language?
A
- Define states, input alphabet, stack alphabet, and transition rules.
- Use transitions to push or pop symbols based on input.
- Ensure final states or empty stack indicate acceptance.
3
Q
How do you show a language is context free?
A
- Construct a CFG that produces all valid strings in the language.
- Ensure grammar rules follow the form A → α where A is a variable and α is a string of terminals and variables.
4
Q
How do you show a Turing Machine is not valid?
A
- Show inconsistency in transition rules.
- Demonstrate non-halting behaviour for all inputs.
- Prove the machine does not produce the expected output.
5
Q
What is the language A-DFA?
A
A-DFA is the set of descriptions of deterministic finite automata (DFAs) that accept a given input string.
6
Q
What is the language A-REX?
A
A-REX is the set of descriptions of regular expressions that match a given input string.
7
Q
What is a the language E-DFA?
A
E-DFA is the set of descriptions of DFAs whose language is empty.
8
Q
What is the language EQ-DFA?
A
EQ-DFA is the set of pairs of DFAs whose languages are identical.
9
Q
How to consider if a function is one-to-one?
A
Definition: A function is one-to-one (injective) if distinct inputs yield distinct outputs.
Method: Show f(a) ≠ f(b) whenever a ≠ b.
10
Q
How to consider if a function is onto?
A
Definition: A function is onto (surjective) if every element in the output set has a preimage.
Method: Show that for every y in the range, there exists x in the domain such that f(x) = y.
11
Q
How to consider if a function is a bijection?
A
Definition: A function is bijective if it is both one-to-one and onto.
Method: Verify injectivity and surjectivity
12
Q
What is the language A-CFG?
A
Definition: A-CFG is the set of context-free grammars that generate a given input string.
13
Q
How do you show a language is decidable?
A
Definition: A language is decidable if there exists a Turing Machine that always halts with an answer.
Method: Construct a TM that determines membership in a finite number of steps.
14
Q
How do you show that A is Turing-recognisable if and only if A reduces to ATM?
A
Definition: If A can be transformed into ATM using a computable function, then A is recognizable.
Method: Show reduction from A to ATM using a mapping function.
If ( A ) is Turing-recognisable, then ( A ) reduces to ( ATM ):
- Definition: Since ( A ) is recognisable, there exists a Turing Machine ( M_A ) that recognises ( A ).
- Reduction Construction: Define a function ( f(w) ) that encodes ( w ) and ( M_A ) into a new input for ( ATM ):- Let ( f(w) = (M_A, w) ) (i.e., an encoding of ( M_A ) running on ( w )).
- Connection to ( ATM ):- If ( M_A ) accepts ( w ), then ( (M_A, w) ) belongs to ( ATM ).
- If ( M_A ) does not accept ( w ), then ( (M_A, w) ) does not belong to ( ATM ).
- Conclusion: The transformation ( f(w) ) is computable, meaning ( A ) is reducible to ( ATM ).
15
Q
What is big-O?
A
Definition: Big-O notation describes an upper bound on the growth rate of a function.
Example: O(n²) means the function grows at most quadratically.
16
Q
How do you show a formula is satisfiable?
A
Definition: A formula is satisfiable if there exists an assignment of values that makes it true.
Method: Find a truth assignment that results in a TRUE evaluation.
17
Q
How do you show that P is closed under union?
A
Theorem: If A and B are in P, then A∪B is in P.
Proof:
Let MA and MB be polynomial-time deciders for A and B respectively.
Let M’ be a machine which runs as follows on the input w:
1. Simulates MA on w. If MA accepts, M’ accepts.
2. Simulates MB on w. If MB accepts M’ accepts. If MB rejects, M’ rejects.
This means M’ accepts w iff w in A OR B, therefore A∪B is recognised by P. Since MA and MB are polynomial, M’ is also polynomial and hence M’ is a polynomial decider for A∪B.
18
Q
How do you show that P is closed under concatenation?
A
Theorem: If A and B are regular languages in P, then AB is in P.
Proof:
Let MA and MB be polynomial-time deciders of A and B respectively. Let M’ be a machine that takes input w (of length n) and runs as follows:
1. repeat the following for all n options of splitting w into two words uv.
2. simulate MA on u. If MA accepts, M’ accepts.
3. simulate MB on v. If MA accepts, M’ accepts.
4. If the above loop ends, then reject.
M’ accepts iff u in A and v in B, so M’ recognises AB. Since MA and MB are polynomial, and since only repeated n times, M’ is also polynomial. Hence, M’ is a polynomial decider for AB.
19
Q
How do you show that P is closed under complement?
A
Theorem: If A is a language in P, then A’ (A complement) is in P.
Proof:
Let M be a polynomial-time decider for A. Let M’ be a machine that simulate m but returns the opposite result.
M’ accepts input w iff w is not in A, so M’ recognises A’. Since M is polynomial, so is M’. Hence M’ is a polynomial decider for A’.
20
Q
What is UHAMPATH? And UHAMPATH-EX?
A
Definition: UHAMPATH is the set of directed graphs with an undirected Hamiltonian path.
UHAMPATH-EX: The decision problem asking whether a Hamiltonian path exists.
21
Q
How do you show UHAMPATH-EX is NP-complete?
A
Definition: UHAMPATH-EX is the problem of deciding whether an undirected Hamiltonian path exists in a given graph.
- Show UHAMPATH-EX is in NP: Verify a given path in polynomial time.
- Reduce from an NP-complete problem (such as HAMPATH): Construct a polynomial-time transformation to UHAMPATH-EX.
- Conclusion: Since both conditions hold, UHAMPATH-EX is NP-complete.
22
Q
What is the TIME class?
A
Definition: TIME(f(n)) represents the set of problems solvable by a deterministic Turing Machine in ( O(f(n)) ) time.
23
Q
How would you Prove that TIME(2^n) = TIME(2^n +1)?
A
Key Idea:
Since a Turing Machine running in ( O(2^n) ), time can trivially execute an extra step in ( O(2^n + 1) ) the classes remain equivalent.
24
Q
What is PSPACE?
A
PSPACE is the class of problems solvable by a deterministic Turing Machine using polynomial space.
Hence, NPSPACE is the class of languages that are decidable in polynomial space on a nondeterministic Turing machine.
25
How do you show PSPACE is closed under union?
1. Assume two languages ( L1 ) and ( L2 ) are in PSPACE.
2. Define a machine ( M' ) that runs both PSPACE algorithms: Simulate both decision procedures in polynomial space.
3. Since polynomial space is preserved, union is in PSPACE.
26
What is radix sort?
Definition: A sorting algorithm that processes numbers digit by digit, grouping elements based on their value at each position.
Complexity: ( O(nk) ), where ( k ) is the number of digits.
27
What is the TIME hierarchy?
Definition: A classification of complexity classes based on increasing time bounds.
Example: TIME(n) ⊆ TIME(n²) ⊆ TIME(2ⁿ).
28
What is the master theorem?
The solution of the recurrence relation
T(n) = aT(n/b) + cn^k
where a and b are integer constants, a ≥ 1, b ≥ 2, and c and k are positive constants, is
T(n) =
1. O(n^(logb^a)) if a > b^k,
2. O(n^k log n) if a = b^k,
3. O(n^k) if a < b^k.
29
Let G be a graph with a matching M and a vertex cover C. Define G, M and C?
( G ): A set of vertices and edges.
( M ): A set of edges where no two edges share a vertex.
( C ): A set of vertices covering all edges in ( G ).
30
What is the approximation algorithm?
Definition: An algorithm that finds a near-optimal solution efficiently for NP-hard problems.
Example: The greedy algorithm for Vertex Cover.
31
What is MAX-CUT?
Definition: The problem of partitioning a graph’s vertices into two sets to maximize the number of edges crossing between them. The maximum cut problem MAX-CUT asks for a largest possible cut in a given graph G.
A cut in an undirected graph is a separation of its vertices into two disjoint subsets S and T.
An edge is called:
▶ cut if it joins a node in S to a node in T;
▶ uncut otherwise.
The size of the cut is the number of cut edges.
Complexity: NP-hard.
32
What is Θ in complexity?
Definition: Represents asymptotically tight bounds for a function.
f(n) = Θ(g(n)) if f(n) = O(g(n)) and f(n) = Ω (g(n)).
Example: (Θ(n2)) and (Ω(n^2)).
33
What is Ω in complexity?
Definition: Represents a lower bound on the growth rate of a function.
f(n) = Ω(g(n)) if positive numbers c and n0 exist such that, for all integers n ≥ n0, f(n) ≥ cg(n)
Example: ( Ω(n) ) means the function grows at least linearly.
34
What is the definition of a Turing machine?
A Turing machine (TM) is a 7-tuple M = (Q, Σ, Γ, δ, q0, qa, qr) where Q, Σ and Γ are finite sets and:
1. Q is the set of states
2. Σ is the input alphabet (not including ⊔)
3. Γ is the tape alphabet (containing all of Σ, plus ⊔ and maybe some more symbols)
4. δ : Q × Γ → Q × Γ × {L, R} is the transition function
5. q0, qa, qr ∈ Q are the start, accept and reject states respectively, with qa ̸= qr
Definition: A mathematical model of computation with an infinite tape, a read/write head, and transition rules.
35
What is a reduction?
Definition: A transformation from one problem to another, preserving solvability.
Usage: Used to prove NP-completeness.
36
What is 3SAT?
Definition: A satisfiability problem where a Boolean formula is in conjunctive normal form (CNF) with three literals per clause.
Complexity: NP-complete.
37
What is a finite automaton?
Definition: A computational model with a finite set of states, transitions, and an input alphabet.
Types: Deterministic (DFA) and Nondeterministic (NFA).
Kleene's theorem: the set of languages regex, nfa and dfa are all the same.
38
What do we call the class of languages recognised by deterministic finite
automata?
Regular languages
39
Which one of the following words is not in the language represented by the regular expression (a^∗b) ∪ (c^∗)?
(A) aaab
(B) aaac
(C) ccc
aaac
40
Which one of the following statements is true?
(A) Finite automata are equivalent to pushdown automata
(B) Context-free grammars are equivalent to pushdown automata
(C) Regular expressions are equivalent to context-free grammars
(B) Context-free grammars are equivalent to pushdown automata
41
Which one of the following statements is true?
(A) All regular languages are finite
(B) All context-free languages are regular
(C) All regular languages are context-free
(C) All regular languages are context-free
42
Which one of the following can recognise any context-free language?
(A) Nondeterministic pushdown automata
(B) Deterministic finite automata
(C) Nondeterministic finite automata
(A) Nondeterministic pushdown automata
43
Which one of the following statements is false?
(A) Every regular language is Turing-recognisable
(B) Every Turing-recognisable language is Turing-decidable
(C) Every Turing-decidable language is Turing-recognisable
(B) Every Turing-recognisable language is Turing-decidable
44
Which one of these cannot simulate a Turing machine?
(A) Enumerators
(B) Context-free grammars
(C) Church’s λ-calculus
(B) Context-free grammars
45
Which one of the following is not Turing-complete?
(A) The universal Turing machine
(B) The Python programming language
(C) A pushdown automaton
(C) A pushdown automaton
46
Which one of the following is uncountable?
(A) The set of all languages over a given alphabet
(B) The set of all Turing machines
(C) The rational numbers Q
(A) The set of all languages over a given alphabet
47
What does it mean for something to be uncountable?
In mathematics, a set is uncountable if it cannot be listed in a sequence, even with infinite time. This means its size (cardinality) is strictly larger than the set of natural numbers.
Uncountable sets have too many elements to be listed in this way, meaning no sequence covers them completely.
Examples:
1. the real numbers
2/ The power set of N
3. The Cantor set, which has an uncountable number of points despite having measure zero.
48
Let M be a Turing machine, and let L(M) be the set of words it accepts.
Which one of the following must be true?
(A) L(M) is countable
(B) L(M) is finite
(C) L(M) is decidable
(A) L(M) is countable
49
Which one of the following is a description of the acceptance problem ATM?
(A) {⟨M, w⟩ | M is a TM that halts on input w}
(B) {⟨M, w⟩ | M is a TM that accepts w}
(C) {⟨M1, M2⟩ | M1 and M2 are TMs and L(M1) = L(M2)}
(B) {⟨M, w⟩ | M is a TM that accepts w}
50
A is a problem that reduces to B. Which one of the following is true?
(A) If A is Turing-recognisable then B is Turing-recognisable
(B) If A is decidable then B is decidable
(C) If B is decidable then A is decidable
(C) If B is decidable then A is decidable
51
What does Rice’s theorem tell us?
(A) All properties of Turing-recognisable languages are trivial
(B) Nontrivial properties of Turing-recognisable languages are undecidable
(C) Nontrivial properties of Turing-recognisable languages are decidable
(B) Nontrivial properties of Turing-recognisable languages are undecidable
52
Which one of the following is true?
(A) Every regular language is undecidable
(B) Every context-free language is regular
(C) Every regular language is decidable
(C) Every regular language is decidable
53
Which one of the following is a description of the emptiness problem ETM?
(A) {⟨M∅, w⟩ | M∅ is a TM that accepts w}
(B) {⟨M1, M2⟩ | M1 and M2 are TMs and L(M1) = L(M2)}
(C) {⟨M⟩ | M is a TM and L(M) = ∅}
(C) {⟨M⟩ | M is a TM and L(M) = ∅}
54
A is a problem that reduces to B. Which one of the following is true?
(A) If A is ATM then B is ATM
(B) If A is undecidable then B is undecidable
(C) If B is undecidable then A is undecidable
(B) If A is undecidable then B is undecidable
55
Which one of the following statements in big-O notation is true?
(A) n log n = O(n^2)
(B) 2n^3 + n^2 = O(n^2)
(C) 2^n = O(n^2)
(A) n log n = O(n^2)
56
What is a description of the class P?
(A) The set of languages with a decider
(B) The set of languages with a polynomial-time decider
(C) The set of languages with a polynomial-time verifier
(B) The set of languages with a polynomial-time decider
57
Which one of the following statements in small-o notation is true?
(A) n^3 = o(n^2)
(B) n^3 = o(2n)
(C) 3n^3 + 10n^2 + 6n − 12 = o(n^3)
(B) n^3 = o(2n)
58
Which one of the following integers is composite?
(A) 1
(B) 17
(C) 20
(C) 20
59
A verifier takes ⟨w, c⟩ as its input. What do we call c?
(A) A constant
(B) A context
(C) A certificate
(C) A certificate
60
What is small-o?
Small-o notation (denoted as o(f(n))) describes an upper bound on a function's growth that is strictly smaller than another given function.
Small-o (( o(f(n)) )) means the function grows strictly slower than the reference function.
Example:
1. ( n = o(n^2) ) : Meaning ( n ) grows strictly slower than ( n^2 ).
2. ( log n = o(n) ) : Logarithmic growth is much slower than linear growth.
61
What is a description of the class NP?
(A) The set of languages with a polynomial-time verifier
(B) The set of languages with a decider
(C) The set of languages with a polynomial-time decider
(A) The set of languages with a polynomial-time verifier
62
Which one of the following containments is false?
(A) NP-hard is a subset of NP
(B) P is a subset of NP
(C) NP-complete is a subset of NP
(A) NP-hard is a subset of NP
63
Let ϕ be given by
ϕ = (x ∨ y ∨ y') ∧ (x ∨ x' ∨ y) ∧ (x' ∨ y').
Which of the following is true?
(A) ⟨ϕ⟩ ∈ 3SAT
(B) ⟨ϕ⟩ ∈ SAT
(C) ⟨ϕ⟩ ∈/ 3SAT and ⟨ϕ⟩ ∈/ SAT
(B) ⟨ϕ⟩ ∈ SAT
64
Which one of the following problems is known to be NP-complete?
(A) The graph isomorphism problem
(B) The composite number problem
(C) The vertex cover problem
(C) The vertex cover problem
The vertex cover problem asks whether a graph contains a vertex cover of a given size.
Formally,
VERTEX-COVER = {⟨G, k⟩ | G is an undirected graph with a k-node vertex cover}
.
65
What is the set of problems that can be solved in polynomial time on a nondeterministic Turing machine?
(A) The exponential-time problems
(B) The NP-hard problems
(C) The class NP
(C) The class NP
66
Unless otherwise specified, when we discuss time complexity what are we
referring to?
(A) Average-case complexity
(B) Worst-case complexity
(C) Best-case complexity
(B) Worst-case complexity
67
The asymptotic complexity symbol Ω refers to which inequality
symbol?
(A) <
(B) ≥
(C) >
(B) ≥
68
Which of the following notations is satisfied by the sum Σn,i=1 i?
(A) o(n)
(B) O(n)
(C) ω(n)
(C) ω(n)
69
What is the master theorem used for?
(A) Evaluating polynomials
(B) Solving recurrence relations
(C) Resolving simultaneous equations
(B) Solving recurrence relations
70
According to the time hierarchy theorem, for a time constructible function t, a language exists that is decidable in what time?
(A) O(t(n)) time, but not o(t(n)) time
(B) Ω(t(n)) time, but not ω(t(n)) time
(C) O(t(n)) time, but not o(t(n)/ log t(n)) time
(C) O(t(n)) time, but not o(t(n)/ log t(n)) time
71
How many comparisons are required for pure binary search to find an entry in a sorted list, in the worst case?
(A) O(1)
(B) O(log n)
(C) O(n)
(B) O(log n)
72
Which sorting algorithm never needs to compare two elements to each other?
(A) Insertion sort
(B) Merge sort
(C) Radix sort
(C) Radix sort
73
Which sorting algorithm splits a list in two based on whether they are
greater or less than a pivot element?
(A) Heapsort
(B) Quicksort
(C) Bucket sort
(B) Quicksort
74
What sort of graphs can be topologically sorted?
(A) Undirected acyclic graphs
(B) Hamiltonian graphs
(C) Directed acyclic graphs
(C) Directed acyclic graphs
75
What is a matching in an undirected graph?
(A) A way of labelling the nodes from 1 to n such that all edges are increasing
(B) A set of edges no two of which have a node in common
(C) A set of nodes each pair of which is joined by an edge
(B) A set of edges no two of which have a node in common
76
How to analyse the complexity of your algorithm?
Definition: Analyzing algorithm complexity means determining how its runtime and space requirements scale as input size n increases.
Steps:
1. Identify the Key Operations: Determine what contributes most to execution time (e.g., loops, recursion).
2. Count the Operations: Express execution steps as a function of ( n ) (input size).
3. Evaluate Growth Rate: Use Big-O, Theta (Θ), and Omega (Ω) Notation to describe best, worst, and average-case complexity.
4. Look for Recursion or Nested Loops:
Single loop → ( O(n) )
Nested loops → ( O(n^2) )
Recursive calls → Use recurrence relations
5. Consider Space Complexity: Analyze memory usage (variables, arrays, recursion depth).
6. Simplify the Complexity Expression: Drop constants and lower-order terms to find the dominant term (e.g., ( O(2n + 3) = O(n) )).
77
How to show that there is no pushdown automaton that recognises a language?
To show that no pushdown automaton (PDA) recognizes a language, need to prove the language is not context-free.
1. Use the Pumping Lemma for CFLs:
1a. The pumping lemma for context-free languages provides a contradiction method.
1b. If a language fails the pumping lemma conditions, it is not context-free → No PDA can recognize it.
2. Use Closure Properties:
2a. CFLs are closed under union, concatenation, and Kleene star but not closed under intersection or complement.
2b. If a language’s complement is context-free but the original is not, it proves that no PDA can recognize it.
78
What is an enumerator?
An enumerator generates all strings belonging to a language and used to describe recursively enumerable languages.
An enumerator consists of:
1. A Turing Machine with an output tape.
2. The ability to list all valid words in the language without repetition.
How It Works:
1. The enumerator runs indefinitely.
2. It prints strings that belong to the target language onto an output tape.
3. The strings can appear in any order (not necessarily sorted or structured).
4. If a language is enumerable, there exists an enumerator that will eventually print every string in the language.
79
What are three properties of enumerators?
1. A language is recursively enumerable (RE) if and only if there exists an enumerator for it.
2. Decidable languages have enumerators that list strings in a structured way and halt.
3. Undecidable languages may still be enumerated, but the process might never halt for certain inputs.
80
What do we use pumping lemmas for?
Proving if a language is not regular.
81
What is the formal language hierarchy?
1. Turing recognisable
2. decidable
3. context free
4. regular
82
What does it mean for a language to be Turing recognisable?
A language ( L ) is Turing-recognisable if there exists a Turing machine (TM) that accepts all strings in ( L ) but may not halt on strings not in ( L ).
Example:
The Halting Problem is Turing-recognisable but not decidable.
83
What is the Halting problem?
The Halting Problem asks:
"Given a program and an input, will the program eventually halt, or will it loop forever?"
84
What is diagonalisation?
Diagonalization is a technique to prove the existence of uncountable sets and demonstrate limits of computation (e.g., the Halting Problem).
85
Prove that the Halting Problem is undecidable.
(Using diagonalisation).
1. Assume a Hypothetical Halt-Decider Exists:
Suppose there exists a universal Turing machine (H) that can decide whether any given program halts on any given input. This means ( H ) takes input ( (P, w) ), where ( P ) is a program and ( w ) is an input for that program, and returns "YES" if (P) halts on (w) and "NO" if ( P ) loops forever.
2. Construct a Self-Referential Paradox:
Define a new machine ( D ) that uses ( H ) but contradicts it:
( D(P) ) takes a program ( P ) as input.
It asks ( H ) whether ( P ) halts when given its own code as input (i.e., ( H(P, P) )).
If ( H ) says "YES" (P halts), then ( D ) loops forever.
If ( H ) says "NO" (P loops forever), then ( D ) halts.
3. Contradiction via Diagonalization:
What happens when ( D ) is given itself as input?
If ( D(D) ) halts, then per its definition, ( H(D, D) ) must have said "NO"—which means it should loop forever (contradiction!).
If ( D(D) ) loops forever, then ( H(D, D) ) must have said "YES"—which means it should halt (contradiction!).
This logical contradiction proves that ( H ) cannot exist.
86
Define the Pumping lemma for regular languages.
If A is a regular language, then there exists an integer p such that if s ∈ A and |s| ≥ p then s may be divided into three pieces s = xyz, where:
1. xy^iz ∈ A for each i ≥ 0,
2. |y| > 0, and
3. |xy| ≤ p.
87
Define the Pumping lemma for context-free languages.
If A is a context-free language, then there exists an integer p (the pumping length) such that if s ∈ A and |s| ≥ p then s may be divided into five pieces s = uvxyz, where:
1. uv^ixy^iz ∈ A for each i ≥ 0,
2. |v| + |y| > 0, and
3. |vxy| ≤ p.
88
What is P?
P: the set of languages that are decidable in polynomial time on a standard Turing machine.
Every context-free language is in P.
Example P: Sorting numbers using Merge Sort or Quick Sort.
89
What is NP?
NP is defined as the set of languages that have polynomial-time verifiers.
A language is in NP iff it is decided by some nondeterministic polynomial-time Turing machine.
Example: The Traveling Salesman Problem (TSP), where finding the shortest route visiting all cities is difficult, but verifying a given route is easy.
NP is a set of problems we cam solve in polynomial time on a nondeterministic TM or verify in polynomial time on a standard TM.
A problem is in NP if a proposed solution can be verified in polynomial time by a deterministic Turing machine. Finding the solution may be difficult, but checking it is easy.
90
What is the P v NP problem?
1. no one has ever shown that an NP problem is not in P. In other words, NP could equal P.
91
What is NP hard?
Every A in NP is polynomial-time reducible to B. Not all NP hard problems are in NP.
Example: The Halting Problem, which determines whether a given program will eventually halt.
An NP-hard problem is one that is at least as hard as the hardest problems in NP, meaning finding a solution might take exponential time, but verifying a solution isn't necessarily polynomial.
92
What is NP complete?
A language B is NP-complete if:
1. B is in NP; and
2. every A in NP is polynomial-time reducible to B (aka NP-hard).
If B is NP-complete and B ≤P C for some C ∈ NP, then C is NP-complete.
Example: The Boolean Satisfiability Problem (SAT), which asks whether a given Boolean formula can be satisfied by some assignment of truth values.
93
True or false: TM's are countable.
True. This is as a bijection can be made from all TM's to N.
94
True or false: Languages are uncountable.
True. Proven via diagonalisation.
95
What is Co-Turing-recognisability?
A language A is co-Turing-recognisable if its complement A' is Turing-recognisable.
Note:
A language is decidable if and only if it is Turing-recognisable and co-Turing-recognisable.
96
Define property and non-trivial.
A property P of a Turing-recognisable language is any statement about that language that
is true or false.
A property P is non-trivial if there is at least one Turing machine whose language satisfies P, and at least one that does not. For example, an empty language is non-trivial whereas a language with finite words is trivial.
97
What is Rice's Theorem?
Let P be a nontrivial property of Turing-recognisable languages. The language LP = {⟨M⟩ | L(M) satisfies P} is undecidable.
98
What is a verifier?
A verifier for a language A is an algorithm V such that
A ={w | V accepts ⟨w, c⟩ for some string c}.
A polynomial-time verifier is one that runs in polynomial time for the length of w.
A language is polynomially verifiable if it has a polynomial-time verifier.
99
What is a graph clique and hence or otherwise define the CLIQUE problem.
A clique in an undirected graph is a subgraph in which every two nodes are connected by an
edge. A k-clique is a clique of k nodes.
The clique (NP) problem is to determine whether a given graph contains a clique of a given size.
Formally,
CLIQUE ={⟨G, k⟩ | G is an undirected graph with a k-clique}.
100
Prove CLIQUE is in NP.
We can solve CLIQUE with a verifier V that takes ⟨G, k, c⟩ as its input. It checks whether c is a list of k nodes that are all connected by edges in G (this check is polynomial in the size
of G): if so, it accepts; if not, it rejects.
V can accept if and only if there is a k-clique in G, so it is a verifier for CLIQUE.
101
What is coNP?
We define coNP as the set of languages that are complements of languages in NP.
102
What is the satisfiability problem (SAT)?
The satisfiability problem is the problem of testing whether a given boolean formula is satisfiable. Formally,
SAT ={⟨ϕ⟩ | ϕ is a satisfiable boolean formula}.
SAT is in P iff P=NP
SAT uses linear space.
103
What is Savitch's theorem?
For any function f : N → R^+,
NSPACE(f(n)) ⊆ SP ACE(f(n)^2)
(So long as f(n) ≥ n for all n).
104
What is EXPTIME?
EXPTIME is the class of languages that are decidable in exponential time on a Turing machine.
105
What is the space hierarchy theorem?
For any space constructible function f : N → N, a language A exists that is decidable in O(f(n)) space but not in o(f(n)) space.
106
What is the time hierarchy theorem?
For any time constructible function t : N → N, a language A exists that is decidable in O(t(n)) time but not in o(t(n)/ log t(n)) time.
107
What is a FSA?
A finite automaton M is a 5-tuple (Q, Σ, δ, q0, F) where:
1. Q is a finite set called the states,
2. Σ is a finite set called the alphabet,
3. δ : Q × Σ → Q is the transition function,
4. q0 ∈ Q is the start state, and
5. F ⊆ Q is the set of accept states.
108
What is a NFA?
A nondeterministic finite automaton (NFA) is a 5-tuple (Q, Σ, δ, q0, F), with the same
definition as a deterministic finite automaton, except that the transition function δ has the
form δ : Q × Σε → P(Q)
109
Define Union, Concatenation and Kleene star.
Given two languages A and B, we define three operations:
▶ Union: A ∪ B = {x | x ∈ A or x ∈ B}
▶ Concatenation: AB = {xy | x ∈ A and y ∈ B} (sometimes written A ◦ B)
▶ Kleene star: A∗ = {x1x2 . . . xk | k ≥ 0 and each xi ∈ A}
Eg: a^∗ba^∗ represents {w | w contains a single b}
110
Define the steps Regex to NFA.
When ripping a state qrip out of the machine, find any paths that go through that state and replace each one with a single regular expression.
111
What is small omega ω notation?
f(n) = ω(g(n)) if lim(n -> infinity) g(n)/f(n) = 0.
112
What is topological sorting?
Given a directed acyclic graph G = (V, E) with n nodes, label the nodes from 1 to n such that, if v is labelled k, then all nodes that can be reached from v by a directed path are labelled with labels > k.
Consider this recursive approach
▶ Recursive step:
▶ Find one node with no in-edges and label it 1
▶ Recursively find a topological sorting for the other n − 1 nodes, then add 1 to all of them
▶ Base case: if n = 1 then we label the only node 1 and this is a solution
▶ Implementation:
▶ Calculate number of in-edges for each node
▶ Create a queue of nodes with no in-edges
▶ Each time a node v is removed, update numbers and queue
113
Define perfect, maximum and maximal matching.
A matching in G is:
▶ perfect if all nodes are matched (|V | must be even)
▶ maximum if it has as many edges as possible for a matching in G
▶ maximal if it cannot be extended by the addition of an edge
114
An approximation algorithm for a minimisation problem is k-optimal if...?
An approximation algorithm for a minimisation problem is k-optimal if it always finds a solution that is no more than k times the size of an optimal solution.
