Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

P5 (CC) Complexity and Computability > Main > Flashcards

Main Flashcards

1
Q

What is the Acceptance problem?

A

ATM

ATM = { < M, w > | M is a TM, M accepts w }

Is recognizable.

Is undecidable.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

In this course what is an algorithm?

A

A turing machine

Stated by the Church-turing theorem

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Formal definition of a turing machine

A

It is a 7-tuple (has 7 components)

  1. Q = finite set of states
  2. Σ = the finite input alphabet
    1. ⊔ ∉ Σ
  3. Γ = the finite tape alphabet
    1. ⊔ ∈ Γ
    2. Σ ⊆ Γ
  4. δ = transition function
  5. q0 = start state
  6. qacc = accept state
    1. qacc != qrej
  7. qrej = reject state
    1. q0, qaccept & qreject ∈ Q
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Definition of when a language is recognizable

A

There are two definitions

  1. If there exist a TM M such that L = L(M).
  2. If there exist a TM M that for any input w accepts iff w ∈ L.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Definition of a decider

A

A TM that halts on all inputs are called deciders

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

When is a language “decidable”

A

A language L is decidable if some TM decides it.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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.)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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>
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Definition of a decidable language

A

There are two definitions

  1. A language L is decidable if there exists a TM M where L = L(M) and M stops on every input.
  2. 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What is the spectrum of languages?

A

((((Regular languages) CF-lang) Decidable) Recognizable (ATM))

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

What is reducibility?

A

It is a method to prove that some problems are undecidable.

To prove that B is undecidable, find a problem A that is known to be undecidable and such that A reduces to B.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

What is a linear bounded automaton?

A

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.

If the machine tries to move its head off either end of the input, the head stays where it is.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

What is a post correspondence problem?

A

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]

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

If A ≤M B and A is undecidable, is B then undecidable?

A

Yes.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

What is a property of recognizable languages?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

What does it mean that a property is trivial?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

Explain running time/time complexity.

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

What does it mean to be an asymptotic upper bound?

A

When f(n) = O(g(n)), we say that g(n) is an asymptotic upper bound for f(n).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

Explain polynomial bounds

A

Bounds of form nc for a constant c > 0.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

Explain exponential bounds.

A

Bounds of form 2n^c for some constant c > 0.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q

What is the time complexity class?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
36
Q

What does a superscript + mean like R+ or N+?

A

R+ all positive real numbers N+ all positive natural numbers

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
37
Q

Explain running time.

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
38
Q

Define PSPACE from NSPACE

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
39
Q

When can Rice’s theorem be used?

A

Given a decision problem:

  1. Examine if it translate to a membership of a languageclass

(“L(M) ∈ S” ? )

  1. 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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
40
Q

What is a Hamiltionian path?

A

A Hamiltonian path in a directed graph G is a directed path that goes through each node exactly once.

Often called HPATH.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
41
Q

What is a verifier?

A

A verifier for a language A is an algorithm V such that
A = {w | V accepts <w> for some strings c}</w>

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
42
Q

When is a language polynomially verifiable?

A

A language is polynomially verifiable if it has a polynomial time verifier.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
43
Q

What is a certificate?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
44
Q

What is NP and what does the name mean?

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
45
Q

When is a language in NP?

A

A language is in NP iff it is decided by some nondeterministic polynomial time TM.

46
Q

What is a clique (CLQ)?

A

A clique in an undirected graph is a subgraph wherein every two nodes are connected by an edge.

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
Q

What does satisfiable mean?

A

A Boolean formula is satisfiable if just one assignment of true and false to the variables make the forumla evaluate to true.

48
Q

When is a function polynomial time computable?

A

A function f : ∑* –> ∑ is polynomial time computable if some polynomial time TM exists that halts on input w producing the output f(w)

49
Q

When is a language polynomial time reducible?

A

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
Q

What is a literal?

A

A literal is a Boolean variable, for example x.

51
Q

When is a Boolean formula in conjunctive normal form?

A

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
Q

When is a Boolean formula a 3-cnf formula?

A

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
Q

What is a vertex cover (VXC)?

A

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
Q

What is space complexity?

A

Space complexity is the complexity of computational problems in terms of the amount of memory that they require.

55
Q

Explain f : N –> N and f(n)

A

f changes some natural number into some natural number. f(n) is the function with input n.

56
Q

What does it mean if we say that M runs in space f(n)?

A

If the space complexity of M is f(n), we say that M runs in space f(n).

57
Q

Is it possible to create TM1 that when given TM2, which recognizes the language L, can check if L is regular

TODO omformuler

A

No TM1 is undecidable

58
Q

What does co-recognizable mean?

A

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
Q

Iff a TM is recognizable and co-recognizable then it is… ?

A

Iff a TM is recognizable and co-recognizable then it is decidable.

60
Q

What is ETM?

A

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
Q

What is the empty language

A

Ø, in other words the language that contains no words

62
Q

What does A ≤m B mean?

A

That A is mapping reducible to language B

63
Q

What does mapping reducible mean?

A

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
Q

What does it mean when a word can be mapped to another?

A

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
Q

Definition of a NP-complete language

A

A language is NP-complete if:

  1. L ∈ NP
  2. For all L1 ∈ NP we have that L1 ≤p L
66
Q

What can NP-complete language be reduced to?

A

An NP-complete language can be only be reduced to another NP-complete language

67
Q

What is 3SAT

A

The same as 3-CNF form.

3SAT is NP-complete like SAT

68
Q

Prove that a language is undecidable

A

Either

prove by rice theorem

or
prove by reduction

69
Q

Is ATM recognizable?

A

Yes

70
Q

Is ATM decidable?

A

No.

71
Q

What is a clause?

A

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
Q

What is prenex normal form?

A

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
Q

When is a formula fully quantified?

A

Every variable has a quantifier

74
Q

Explain Savitch’s theorem

A

NSPACE(f(n)) ⊆ DSPACE((f(n))2)

Savitch’s theorem can be used to show that PSPACE = NPSPACE.

75
Q

What is a k-Clique?

A

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
Q

What is PSPACE

A

The set of decision problem that can be solved by a TM using a polynomial amount of space.

77
Q

What is NTIME?

A

The set of decision problem that can be solved by a nondeterministic TM which in time O(f(n)).

78
Q

Define NP

A

NP = {L | L has a polynomial verifier}

79
Q

How do you convert a multitape to a singletape?

A

multitape O(f(n)) = singletape O(f2(n))

Example:
Multitape O(n<sup>2</sup>) = singletape O((n<sup>2</sup>)<sup>2</sup>)

We have a math rule: singletape O(n2*2) = O(n4)

80
Q

Explain polynomial reduction

A

L1 ≤p L

Means L1 is reducible to L, and performing the reduction takes at most polynomial time.

81
Q

Explain and define EQTM

A

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
Q

What is the compliment of a language

A

The compliment of the set A is every string not in A.

83
Q

What does the ∀ symbol mean?

A

Means for all

84
Q

What does A ~ B mean?

A

That A and B are equipotent.

85
Q

What is the difference between a countable and an uncountable amount?

A

R is an uncountable amount as you can always add another number right of the decimal.

N is a countable amount.

86
Q

HALTTM

A

A TM that can decide if a given TM halts.

It is undecidable, recognizable and not co-recognizable.

87
Q

What is a quantifier?

A

∀ (for all) and ∃ (there exists) are two of many quantifiers.

88
Q

What is a unquantified boolean formula?

A

A part of a boolean formula without quantifiers.

89
Q

What is the difference between SPACE and DSPACE?

A

They are not different they are the same thing.

90
Q

Define NP from NTIME

A
91
Q

What is the Turing-Church thesis?

A

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
Q

The relation between the time complexity of nondeterministic TMs and standard TMs.

A

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
Q

Class co-NP

A

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
Q

SUBSET-SUM (S-sum) problem

A

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
Q

Explain the Cook-Levin Theorem

A

This explains that SAT is NP-complete, so any NP problem can be reduced to SAT in polynomial time .

96
Q

What is Rice’s Theorem and Proof by Reduction used for?

A

To prove that a language is undecidable.

97
Q

If A ≤m B and B is recognizable is A recognizable?

A

Yes, A is recognizable.

98
Q

If A ≤m B and A is recognizable is B recognizable?

A

Yes!

99
Q

A ≤M B and B is undecidable, is A then undecidable

A

Not necessarily

100
Q

What is a reliable function?

A

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
Q

Define a graph G

A

G = (V, E)

*V = collection of all vertices in G
E = collection of all edges in G*
102
Q

Is O(n) polynomial time?

A

Yes

103
Q

What is the class P?

A

The collection of languages that can be decided by a deterministic TM in polynomial time.

104
Q

Define the language CLIQUE

A

CLIQUE = { < G, k > | G is a non-oriented graph, G has a clique of size k}

CLIQUE ∈ NP

105
Q

Define the class P

A

P = { L | L ∈ TIME(nk), k ≥ 0 }

106
Q

What does it mean that two TMs are polynomially equivalent?

A

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
Q

A ≤M B and B is decidable, is A then decidable?

A

Yes

108
Q

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?

A

∀w. w ∈ A <==> f(w) ∈ B

109
Q

Define NPSPACE from NSPACE

A
110
Q

Define PSPACE from SPACE

A

P5 (CC) Complexity and Computability (1 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions