1
Q
What is the Acceptance problem?
A
ATM
ATM = { < M, w > | M is a TM, M accepts w }
Is recognizable.
Is undecidable.
2
Q
In this course what is an algorithm?
A
A turing machine
Stated by the Church-turing theorem
3
Q
Formal definition of a turing machine
A
It is a 7-tuple (has 7 components)
- Q = finite set of states
- Σ = the finite input alphabet
- ⊔ ∉ Σ
- Γ = the finite tape alphabet
- ⊔ ∈ Γ
- Σ ⊆ Γ
- δ = transition function
- q0 = start state
- qacc = accept state
- qacc != qrej
- qrej = reject state
- q0, qaccept & qreject ∈ Q
4
Q
The transition function (δ)
A
δ(q,a) = (r,b,D)
δ tells us how the machine reacts if we are in some state q while the head reads a.
Then enter a new state r, replace a with some symbol b, and move in some direction D (left or right)
A nondeterministic TM’s transition function can contain several possibilities for the same situation (any one of the parentheses):
δ(q,a) = { (r,b,D), … (rk, bk, Dk) }
Can also be written as sets:
δ: Q x Γ –> Q x Γ x {L,R}
Q (all states) and the tape alphabet, transition to another Q and tape alphabet along with a left or rigt movement of the tapehead.
5
Q
Definition of a configuration
A
A configuration of turing machine M is a string: uqav
- u, v ∈ Γ*
- u = portion left of head
- v = nonblank portion right of head
- q ∈ Q
- current state
- a ∈ Γ
- symbol currently scanned
Written: q0110 then 0q110 and so forth.
6
Q
What is L(M)
A
The collection of strings that M accepts is the language of M or the language recognized by M, denoted L(M)
7
Q
Definition of when a language is recognizable
A
There are two definitions
- If there exist a TM M such that L = L(M).
- If there exist a TM M that for any input w accepts iff w ∈ L.
8
Q
Definition of a decider
A
A TM that halts on all inputs are called deciders
9
Q
What does it mean when a decider “decides L”
A
That it will accept on any input w where w ∈ L, and reject on any input where w ∉ L
10
Q
When is a language “decidable”
A
A language L is decidable if some TM decides it.
11
Q
What is the relation between Multi-tape TMs and Single-tape TMs?
A
Every multi-tape TM has an equivalent single-tape TM.
12
Q
What is a Nondeterministic TM?
A
At any point in a computation the machine may proceed according to several possibilities.
A Nondeterministic TM can from one state go to several different states with the same input.
13
Q
What is the relation between nondeterministic and deterministic TMs?
A
Every nondeterministic TM has an equivalent deterministic TM.
A NTM with n states converted to a DTM may have up to 2n states
14
Q
What is an enumerator?
A
- A TM which prints the content on its tape.
- The printed set of strings represents the language recognized by the enumerator.
- An enumerator starts with the blank input on its tape
- It might print an infinite list of strings
- It might generate strings in any order
- It might print repeatedly the same string
15
Q
What is the terminology for describing TMs?
A
- Formal description
- Spells out in full the TM’s states, transition function, etc.
- The lowest level of description
- Quickly becomes very complex, even for simple problems
- Implementation description
- We use English to describe the way the TM works
- We describe how the TM moves its tape head
- We describe how the TM uses the tape (stores information)
- We do not give details about states or transition functions
- High-level description
- We use English to describe an algorithm
- We do not provide details about the use of the machine (tape head, tape, states, etc.)
16
Q
What kind of input can a TM take?
A
The input of a TM is always a string.
- If we use other objects as input, e.g. polynomials, we need to find a way to encode the object into a string
- input 0 => input <0>
- input 01,02,…,0k => input <01,02,…,0k>
17
Q
Definition of a decidable language
A
There are two definitions
- A language L is decidable if there exists a TM M where L = L(M) and M stops on every input.
- A language L is decidable if there exists a TM M such that we for all strings w have that M accepts w if w ∈ L and rejects w if w ∉ L
18
Q
What is the spectrum of languages?
A
((((Regular languages) CF-lang) Decidable) Recognizable (ATM))
19
Q
What does it mean when a function is injective?
A
It means that it is one-to-one. It does not map two different elements of A to the same element of B.
20
Q
What does it mean when a function is surjective?
A
A function f: A –> B is surjective (onto) if all the elements of B are associated to some element of A.
21
Q
What is a bijective function?
A
A function f: A –> B is bijective if each element of A corresponds to a unique element of B and each element of B corresponds to a unique element of A, i.e., f is injective and surjective
22
Q
When are sets equipotent?
A
Two sets A and B are equipotent, written A ~ B if there exists a bijective function from A to B.
Intuitively, two sets are equipotent iff they have the same “number” of elements.
The class of all sets equipotent to a given set is called a cardinal.
23
Q
What is a universal turing machine?
A
A universal TM U:
- is a “universal simulator” of TMs. (It simulates any possible TM)
- the initial part of the tape describes all the instructions of a TM T, and after reading this part of the tape U behaves like T.
24
Q
What is a reduction?
A
A reduction is a way of converting one problem to another problem in such a way that a solution to the second problem can be used to solve the first problem.
Problem A reduces to Problem B
- A solution to B provides a solution to A
- Solving A is not harder than solving B
- If B is decidable then A is decidable
- If A is undecidable then B is undecidable
25
What is reducibility?
It is a method to prove that some problems are undecidable.
## Footnote
To prove that B is undecidable, find a problem A that is known to be undecidable and such that A reduces to B.
26
What is a linear bounded automaton?
A linear bounded automaton is a TM such that the tape head is not permitted to move off the portion of the tape containing the input.
## Footnote
If the machine tries to move its head off either end of the input, the head stays where it is.
27
What is a post correspondence problem?
Post correspondence problem: It is undecidable whether a collection of dominos has a match.
A collection of dominos: [a | ab], [b | ac], [abc | ac], [ab | bc]
A match is a list of dominos (repetition permitted) so that the string we get by reading off the symbols on the top is the same as the string of symbols on the bottom.
Example of a match:
[a | ab], [b | ca], [ca | a], [a | ab], [abc | c]
28
If A ≤M B and A is undecidable, is B then undecidable?
Yes.
29
What is a property of recognizable languages?
A class of languages S is called a property of recognizable languages if all the members of S are recognizable languages, i.e, for every L ∈ S there exists a TM that recognizes L.
30
What does it mean that a property is trivial?
A trivial property is true either for all languages or for no languages.
If you can prove for a property of some set of laguages that two laguages L1 and L2 exist such that L1 ∈ S and L2 ∉ S, then that property is non-trivial.
*If S is not trivial, then it is non-trivial.*
31
Explain running time/time complexity.
Let M be a deterministic TM that halts on all inputs.
The running time or time complexity of M is the function:
f: N --\> N
where f(n) is the maximum number of steps that M uses on any input of length n.
If f(n) is the running time of M, we say that M runs in time f(n) and that M is an f(n) time Turing machine.
32
What does it mean to be an asymptotic upper bound?
When f(n) = O(g(n)), we say that g(n) is an asymptotic upper bound for f(n).
33
Explain polynomial bounds
Bounds of form nc for a constant c \> 0.
34
Explain exponential bounds.
Bounds of form 2n^c for some constant c \> 0.
35
What is the time complexity class?
Let t: N --\> R+ be a function. The time complexity class TIME(t(n)) is the collection of all languages that are decidable by a 0(t(n)) time Turing Machine.
36
What does a superscript + mean like R+ or N+?
R+ all positive real numbers N+ all positive natural numbers
37
Explain running time.
Let N be a nondeterministic TM that is a decider. The running time of N is the function f: N --\> N where f(n) is the maximum number of steps that N uses on any branch of its computation on any input of length n.
38
Define PSPACE from NSPACE
39
When can Rice's theorem be used?
Given a decision problem:
1. Examine if it translate to a membership of a languageclass
("L(M) ∈ S" ? )
2. Examine if S is a non-trivial property, by finding a language that has it and another that does not have it.
If 1 and 2 is true, then Rice's theorem can be used.
40
What is a Hamiltionian path?
A Hamiltonian path in a directed graph G is a directed path that goes through each node exactly once.
## Footnote
*Often called HPATH.*
41
What is a verifier?
A verifier for a language A is an algorithm V such that
A = {w | V accepts for some strings c}
## Footnote
The time of a verifier is measured in terms of |w|
A polynomial time verifier is a verifier that runs in polynomial time (in the length of w)
42
When is a language polynomially verifiable?
A language is polynomially verifiable if it has a polynomial time verifier.
43
What is a certificate?
A verifier uses a string. This is called a certificate or a proof of membership in the language.
A certificate for a string ∈ HPATH is an example Hamiltonian path from s to t.
44
What is NP and what does the name mean?
* NP is the class of languages that are decided by nondeterministic polynomial TMs.
* NP is _decidable_.
* The name: nondeterministic polynomial time.
* NP has a polynomial verifier
45
When is a language in NP?
A language is in NP iff it is decided by some nondeterministic polynomial time TM.
46
What is a clique (CLQ)?
A clique in an undirected graph is a subgraph wherein every two nodes are connected by an edge.
## Footnote
A k-clique is a clique with k nodes.
A Clique is where every node is connected to every node.
A Clique can appear in a graph where each node is not connected:
If a graph has 5 nodes and 3 of them are all connected to eachother those three are a Clique.
47
What does satisfiable mean?
A Boolean formula is satisfiable if just one assignment of true and false to the variables make the forumla evaluate to true.
48
When is a function polynomial time computable?
A function f : ∑\* --\> ∑ is polynomial time computable if some polynomial time TM exists that halts on input w producing the output f(w)
49
When is a language polynomial time reducible?
A language A is polynomial time reducible to language B, written A ≤p B, if there exists a polynomial time computable function f : ∑\* --\> ∑\* such that for any w ∈ ∑\*, w ∈ A iff f(w) ∈ B.
f is called the _polynomial time reduction_ of A to B.
50
What is a literal?
A literal is a Boolean variable, for example x.
51
When is a Boolean formula in conjunctive normal form?
A Boolean formula is in conjunctive normal form (cnf-formula) if it is a conjunction of clauses.
(x \/ !x \/ y \/ z) /\ (x \/ y) /\ (x \/ !y \/ !z), (x \/ y \/ !z) /\ x /\ !z are cnf-formulas
52
When is a Boolean formula a 3-cnf formula?
A Boolean formula is a 3-cnf formula if it is a cnf-formula and all the clauses have at most three literals
(x \/ y \/ !z) /\ (x \/ !y \/ !u) /\ (!u \/ x \/ z)
53
What is a vertex cover (VXC)?
If G is an undirected graph, a vertex cover of G is a set of nodes where every edge of G touches one of these nodes.
54
What is space complexity?
Space complexity is the complexity of computational problems in terms of the amount of memory that they require.
55
Explain f : N --\> N and f(n)
f changes some natural number into some natural number. f(n) is the function with input n.
56
What does it mean if we say that M runs in space f(n)?
If the space complexity of M is f(n), we say that M runs in space f(n).
57
Is it possible to create TM1 that when given TM2, which recognizes the language L, can check if L is regular
## Footnote
**TODO omformuler**
No TM1 is undecidable
58
What does co-recognizable mean?
A language is co-recognizable if its compliment is recognizable.
* We have a TM M that recognizes the language
* We also have a TM M(with a line over it) that recognizes all words that are not in the language L
* If and only if M(with a line over it) is recognizable then M is co-recognizable and if M is recognizable then M(with a line over it) is co-recognizable
59
Iff a TM is recognizable and co-recognizable then it is... ?
Iff a TM is recognizable and co-recognizable then it is decidable.
60
What is ETM?
A TM that can say if a given TM recognizes the empty language
undecidable, unrecognizable, co-recognizable
ETM = { \< M \> | M is a turing machine where L(M) = Ø}
61
What is the empty language
Ø, in other words the language that contains no words
62
What does A ≤m B mean?
That A is mapping reducible to language B
63
What does mapping reducible mean?
If A is mapping reducible to B then all words in A can be mapped to words in B (All words in B does not need to be able to be mapped to A)
64
What does it mean when a word can be mapped to another?
If we have the languages A {1, 10, 101} and B{0, 01, 010}. Then if we have a function that swaps all 0s to 1s and all 1s to 0s. Then you can say that the words in A can be mapped to B (And the other way around).
65
Definition of a NP-complete language
A language is NP-complete if:
1. L ∈ NP
2. For all L1 ∈ NP we have that L1 ≤p L
66
What can NP-complete language be reduced to?
An NP-complete language can be only be reduced to another NP-complete language
67
What is 3SAT
The same as 3-CNF form.
3SAT is NP-complete like SAT
68
Prove that a language is undecidable
Either
prove by rice theorem
or
prove by reduction
69
Is ATM recognizable?
Yes
70
Is ATM decidable?
No.
71
What is a clause?
A clause is an expression formed from a finite collection of literals that is true either whenever at least one of the literals that form it is true or when all of the literals that form it are true
(x \/ y \/ z) is a clause since if either *x* or *y* or *z* is true the entire expression is true.
72
What is prenex normal form?
A fully quentified boolean formula can be assumed to have a very specific form, called prenex normal form.
It has 2 parts:
1. Only contains quantifiers
2. Only contains an unquantified boolean formula.
73
When is a formula fully quantified?
Every variable has a quantifier
74
Explain Savitch's theorem
NSPACE(f(n)) ⊆ DSPACE((f(n))2)
*Savitch's theorem can be used to show that PSPACE = NPSPACE.*
75
What is a k-Clique?
A k-clique is a clique with k nodes.
A 3-clique is a clique with three nodes.
A 4-clique also contains 3-cliques (it contains 4 different 3-cliques).
76
What is PSPACE
The set of decision problem that can be solved by a TM using a polynomial amount of space.
77
What is NTIME?
The set of decision problem that can be solved by a nondeterministic TM which in time O(f(n)).
78
Define NP
NP = {L | L has a polynomial verifier}
79
How do you convert a multitape to a singletape?
multitape O(f(n)) = singletape O(f2(n))
## Footnote
```
Example:
Multitape O(n2) = singletape O((n2)2)
```
We have a math rule: singletape O(n2*2) = O(n4)
80
Explain polynomial reduction
L1 ≤p L
Means L1 is reducible to L, and performing the reduction takes at most polynomial time.
81
Explain and define EQTM
A TM that can take two TM's and tell if they are equivalent.
It is undecidable, unrecognizable and not co-recognizable.
*EQTM = { \< M1 , M2\> | M1 and M2 are TMs, L(M1) = L(M2) }*
82
What is the compliment of a language
The compliment of the set A is every string not in A.
83
What does the ∀ symbol mean?
Means for all
84
What does A ~ B mean?
That A and B are equipotent.
85
What is the difference between a countable and an uncountable amount?
R is an uncountable amount as you can always add another number right of the decimal.
N is a countable amount.
86
HALTTM
A TM that can decide if a given TM halts.
It is undecidable, recognizable and not co-recognizable.
87
What is a quantifier?
∀ (for all) and ∃ (there exists) are two of many quantifiers.
88
What is a unquantified boolean formula?
A part of a boolean formula without quantifiers.
89
What is the difference between SPACE and DSPACE?
They are not different they are the same thing.
90
Define NP from NTIME
91
What is the Turing-Church thesis?
Every TM can be described as an algorithm, and reverse.
Algorithms = Turing machines
Has not been proven, but has never not been the case.
92
The relation between the time complexity of nondeterministic TMs and standard TMs.
Every NTM can be simulated by a DTM but takes exponentially longer
* NTM: O(f(n))
* The complexity will be: 2O(f(n)) on a DTM
93
Class co-NP
A decision problem is a member of Co-NP if its compliment is a member of
NP.
Wikipedia: "*Co-NP is the set of problems that can have counter examples to their proofs.*"
If L is in both NP and Co-NP then it is probably not NP-complete.
* NP is concerned with yes answers to a decision problem
* Co-NP is concerned with the No answer to a decision problem.
94
SUBSET-SUM (S-sum) problem
The problem is this: given a set (or multiset) of integers, is there a non-empty subset whose sum is zero? For example, given the set {−7, −3, −2, 5, 8}, the answer is yes because the subset {−3, −2, 5} sums to zero.
S-SUM is NP-complete
95
Explain the Cook-Levin Theorem
This explains that SAT is NP-complete, so any NP problem can be reduced to SAT in polynomial time .
96
What is Rice's Theorem and Proof by Reduction used for?
To prove that a language is undecidable.
97
If A ≤m B and B is recognizable is A recognizable?
Yes, A is recognizable.
98
If A ≤m B and A is recognizable is B recognizable?
Yes!
99
A ≤M B and B is undecidable, is A then undecidable
Not necessarily
100
What is a reliable function?
Example:
Language A ≤M B.
The function f swaps 0s and 1.
* If the function gets a word (010) that is in A it returns a word (101) that is in B.
* If the function gets a word that is not in A it will return a word that is not in B.
101
Define a graph G
G = (V, E)
```
*V = collection of all vertices in G
E = collection of all edges in G*
```
102
Is O(n) polynomial time?
Yes
103
What is the class P?
The collection of languages that can be decided by a deterministic TM in polynomial time.
104
Define the language CLIQUE
CLIQUE = { \< G, k \> | G is a non-oriented graph, G has a clique of size k}
CLIQUE ∈ NP
105
Define the class P
P = { L | L ∈ TIME(nk), k ≥ 0 }
106
What does it mean that two TMs are polynomially equivalent?
All reasonable deterministic computational models are polynomially equivalent.
That is, any one of them can simulate another with only a polynomial increase in running time.
* We know that multi-tape and single-tape TMs are polynomially equivalent.
* We do not yet know if NTMs and DTMs are polynomially equivalent.
107
A ≤M B and B is decidable, is A then decidable?
Yes
108
When told to prove that for example A is decidable since A ≤m B, (B is decidable) what is the sentence that you have to write after explaining that Mf is reliable?
∀w. w ∈ A \<==\> f(w) ∈ B
109
Define NPSPACE from NSPACE
110
Define PSPACE from SPACE
P5 (CC) Complexity and Computability
flashcards
Decks in class (1)
# Cards
