CECS 329-Midterm 2

Which statement about the cardinalities of the set of natural numbers N = {1, 2, 3, ... } and the set of even natural numbers 2N = {0, 2, 4, 6, ... } is correct?

|N| = |2N|

Which statement about the cardinalities of the set A and its power set P(A) is correct?

|A| < |P(A)|

How are the cardinalities of the sets N of natural numbers, Q of rational numbers, and R of real numbers related to each other?

|N| = |Q| < |R|

Let Σ be an alphabet. A language A ∈ Σ * is called regular if there is a finite automaton M such that... A is the language of 𝑀.

𝐴=𝐿(𝑀).

𝑀 recognizes 𝐴. All other options are correct

All other options are correct.

All languages are regular.

No

GNFAs, NFAs, and DFAs are all equivalent, i.e. they all recognize the same class of languages.

Yes, they all recognize regular languages.

Which of the following languages are decidable?

ANFA = {

ADFA = {

EQDFA = {

ATM = {| A is a Tm and accepts A}

ANFA = {

ADFA = {

EQDFA = {

What does the Church-Turing-Thesis say?

Any real-world computation can be translated into an equivalent computation performed by a Turing machine.

What is a Turing Machine?

A theoretical machine to model and reason about computation.

Decidability of languages does not depend on the model of computation.

True

The complexity class P does depend on the model of computation

Yes, but it is equivalent for all reasonable deterministic models of computation.

Languages in P can be efficiently decided. Yes, that's the meaning of the class P.

Not at all, problems in P generally have a high time complexity.

Not necessarily. The time complexity might be 𝑂(𝑛𝑘) whith a very large value for 𝑘.

Not necessarily. The time complexity might be O(n^k) with a very large value for k

Which of the following statements are correct:

All decidable languages are in the complexity class P.

All languages in P are T-recognizable.

All languages in P are decidable.

All regular languages are in the complexity class P

All languages in P are T-recognizable.

All languages in P are decidable.

All regular languages are in the complexity class P

What is the definition of the Bachmann-Landau big O notation? f(n) in O(g(n)) <->

∃k > 0 ∃n0 ∀n > n0 |f(n)| <= kg(n)

What is the known relationship between the complexity classes N and NP?

P ⊆ NP (P is subset of NP)

What is the definition of mapping reducibility (also called many-one reducibility)?

if there is a computable function f : Σ∗ → Γ∗ such that w ∈ A <=> f(w) ∈ B .

Is it true that TIME(t(n)) ⊆ SPACE(t(n))?

Yes, because we need at least one computational step to write into a new memory cell.

A language B is NP-Complete iff

... B is in NP and any language A in NP can be polynomially reduced to B.

Which of these languages are NP-Complete? HALT (Halting Problem)

SAT (Boolean Satifiability)

PATH (Path Problem)

3-SAT (3-CNF Boolean Satifiability)

SAT and 3-SAT

What is the definition of an alphabet Σ ?

Σ is a non-empty, finite set.

A language A ⊆ Σ ∗ is polynomial time reducible to the language B ⊆ Γ ∗ and we write A ≤p B

... if there is a function f : Σ∗ → Γ∗ computable in polynomial time such that w ∈ A <=> f(w) ∈ B .

If we would find a proof for SAT ∈ P then this would imply that

P = NP

It allows you to solve all of NP in P

Are all regular languages in the complexity class P ?

Yes, because a DFA reads one input symbol per state transition.

How can we describe the complexity classes P and NP informally?

NP = All languages where we can verify membership quickly.

P = All languages where we can test membership quickly

Which of the following boolean expressions are in 3-CNF?

(u ∨ y! ∨ z) ∧ (x ∨ v ∨ z) ∧ (x ∨ y! ∨ w!)
(x ∨ y! ∨ z) ∧ (x ∨ y ∨ z) ∧ (x ∨ y! ∨ z!)
(u ^ y! ^ z) V (x ^ v ^ z) V (x ^ y! ^ w!)
(x ^ y! ^ z) V (x ^ y ^ z) V (x ^ y! ^ z!)

(u ∨ y! ∨ z) ∧ (x ∨ v ∨ z) ∧ (x ∨ y! ∨ w!)

(x ∨ y! ∨ z) ∧ (x ∨ y ∨ z) ∧ (x ∨ y! ∨ z!)

Is SAT NP-complete?

Yes

Two models of computation are polynomially related if each can simulate the other with a polynomial overhead, i.e. if the computation takes t(n) time on one model it may take t k(n) time on the other model, for some k . Which of the following are polynomially related to a 1-tape Turing Machine?

random access machines (RAM)

multi-dimensional Turing Machines

multi-tape TMs

cellular automata

All reasonable deterministic models are polynomial related: random access machines (RAM), multi-dimensional Turing Machines, multi-tape TMs, cellular automata

Alan Turing proved the undecidability of the halting problem. Which proof technique from set theory did inspire Turing?

Cantor's diagonal argument

What is the output (on the tape) of the Turing Machine M on input 10010111 where

10011000

Is the complexity class P closed under union, ie. does L1 ∈ P and L2 ∈ P imply that L1 ∪ L2 ∈ P?

Yes

Is the following formula satisfiable? (x ∨ y) ∧ (x ∨ y!) ∧ (x! ∨ y) ∧ (x! ∨ y!)

No

Which of the following are true?

3^n ∈ 2^O(n)

n log n ∈ O(n^2)

2n ∈ O(n)

n^2 ∈ O(n)

3^n ∈ 2^O(n)

n log n ∈ O(n^2)

2n ∈ O(n)

Turing machines can...

write

read

write or read

write or read

On input w, a TM M may...

halt or loop

A is T-recognizable if?

if A = L(M) may be found in some TM M in which L(M) is the collection of strings that M accepts

A is T-decidable if?

𝐴 = 𝐿(𝑀) for some TM decider 𝑀. (halts on all inputs and decides to accept or reject)

No loop

Why pick a specific model?

Choice of model doesn't matter. All reasonable models are equivalent in power.

What is a multi-tape Turing machine?

ordinary turing machine with several tapes. Has input tape and work tape that all read/write

Can multi-tape do more than single tape?

No because all models of computation are equivalent in power.

What is a nondeterministic Turing machine?

At any point in a computation, the machine may proceed according to several possibilities.

The computation of a nondeterministic Turing machine is a tree whose branches

correspond to different possibilities for the machine. If some branch of the computation

leads to the accept state, the machine accepts its input.

What is the difference between a Nondeterministic TM and a Deterministic TM?

NTM transition function 𝛿: Q×Γ → 𝒫( 𝑄×Γ× {L, R} ).

What is a turing enumerator?

A deterministic TM with a printer.

It starts on a blank tape and it can print strings 𝑤! , 𝑤" , 𝑤# , ... possibly going forever if it doesn't halt. Its language is the set of all strings it prints. It is a generator, not a recognizer.

For enumerator 𝐸 we say 𝐿 𝐸 = 𝑤 𝐸 prints 𝑤}.

What is Hilbert's 10th problem?

devise an algorithm that tests whether a polynomial

has an integral root. He did not use the term algorithm but rather "a process according to which it can be determined by a finite number of operations."

Why couldn't Hilbert's 10th problem be solve?

Because at the time of release, there was no formal definition for algorithm, i.e. it couldn't be stated that D is not decidable.

Is ADFA decidable?

Yes, ADFA is decidable.

Give TM 𝐷A−DFA that decides 𝐴DFA .

𝐷A−DFA = "On input 𝑠

1. Check that 𝑠 has the form 𝐵,𝑤 where

𝐵 is a DFA and 𝑤 is a string; reject if not.

2. Simulate the computation of 𝐵 on 𝑤.

3. If 𝐵 ends in an accept state then accept.

If not then reject."

Is ANFA decideable?

Yes.

Give TM 𝐷A−NFA that decides 𝐴NFA .

𝐷A−NFA = "On input 𝐵,𝑤

1. Convert NFA 𝐵 to equivalent DFA 𝐵′.

2. Run TM 𝐷A−DFA on input 𝐵′,𝑤 . [ Recall that 𝐷A−DFA decides 𝐴DFA ]

3. Accept if 𝐷A−DFA accepts.

Reject if not."

what is acceptance problem, emptiness problem, and equivalent problem?

algorithms for testing whether a finite automaton accepts a string, whether

the language of a finite automaton is empty, and whether two finite automata are

equivalent.

Is EDFA decidable?

Yes.

Proof: Give TM 𝐷E−DFA that decides 𝐸DFA .

𝐷E−DFA = "On input 𝐵 [IDEA: Check for a path from start to accept.]

1. Mark start state.

2. Repeat until no new state is marked:

Mark every state that has an incoming arrow

from a previously marked state.

3. Accept if no accept state is marked.

Reject if some accept state is marked."

Is EQDFA decidable?

Yes

Proof: Give TM 𝐷EQ−DFA that decides 𝐸𝑄DFA .

𝐷EQ−DFA = "On input 𝐴, 𝐵 [IDEA: Make DFA 𝐶 that accepts 𝑤 where 𝐴 and 𝐵 disagree.]

1. Construct DFA 𝐶 where 𝐿 𝐶 = 𝐿 𝐴 ∩ 𝐿 𝐵 ∪ 𝐿 𝐴 ∩ 𝐿 𝐵 . (Symmetric difference)

2. Run 𝐷E−DFA on 〈𝐶〉 .

3. Accept if 𝐷E−DFA accepts.

Reject if 𝐷E−DFA rejects."

Is ACFG decidable?

Yes

Proof: Give TM 𝐷A−CFG that decides 𝐴CFG .

𝐷A−CFG = "On input 𝐺,𝑤

1. Convert 𝐺 into CNF.

2. Try all derivations of length 2|𝑤| − 1.

3. Accept if any generate 𝑤.

Reject if not.

Is ECFG decidable?

yes.

Proof:

𝐷E−CFG = "On input 𝐺 [IDEA: work backwards from terminals]

1. Mark all occurrences of terminals in 𝐺.

2. Repeat until no new variables are marked

Mark all occurrences of variable A if

A → B!B"⋯B# is a rule and all B% were already marked.

3. Reject if the start variable is marked.

Accept if not."

Is every CFL decidable?

yes

Is EQCFG decidable?

NO, IT IS NOT.

IS AMBIGCFG decidable?

NO, IT IS NOT.

Is ATM decidable?

NO, IT IS NOT.

Is ATM T-recognizable?

Yes.

What is a universal Turing machine?

capable of simulating any other Turing machine from the description of that machine

What is a countable set?

A set A is countable if either it is finite or it has the same size as N. Let N be the set of natural numbers {1, 2, 3, . . .}

Are both ℤ and ℚ+ countable?

Yes

Is R uncountable?

Yes, because Contor's diagonalization method shows a number 𝑥 ∈ ℝ that is missing from the list.

Let L= set of all languages over alphabet Σ. Is L countable?

L is uncountable

Is the set of all Turing machines countable? M= all Turing machines.

Yes because each Turing machine M has an encoding into a string ⟨M⟩. ({<𝑀>| 𝑀 is a TM} ⊆ Σ∗).

Is Σ* countable?

Yes

Are all languages decidable or even T-recognizable?

No, because there are uncountably many languages yet only countably many Turing machines. Because each Turing machine can recognize a single language and there are more languages than Turing machines, some languages are not recognized by any Turing machine.

What is co-Turing-recognizable?

the complement of a Turing-recognizable language.

Is the complement of ATM T-recognizable?

No

A language is decidable when?

A language is decidable iff it is Turing-recognizable and co-Turing-recognizable.

In other words, a language is decidable exactly when both it and its complement are Turing-recognizable.

What is reducibility?

the primary method for proving that problems are computationally unsolvable. 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.

Is HALT TM undecidable?

Yes.

Use our knowledge that 𝐴TM is undecidable to show other

problems are undecidable.

What is the concept of Reducibility?

If we have two languages (or problems) 𝐴 and 𝐵, then

𝐴 is reducible to 𝐵 means that we can use 𝐵 to solve 𝐴.

Example 1: Measuring the area of a rectangle

is reducible to measuring the lengths of its sides.

Example 2: We showed that 𝐴NFA is reducible to 𝐴DFA .

If 𝐴 is reducible to 𝐵 then solving 𝐵 gives a solution to 𝐴.

Is ETM undecidable?

Yes.

Proof by contradiction. Show that 𝐴TM is reducible to 𝐸TM.

Assume that 𝐸TM is decidable and show that 𝐴TM is decidable (false!).

What is Mapping Reducibility?

𝐴 is mapping-reducible to 𝐵 (𝐴 ≤" 𝐵) if there is a computable function 𝑓 where 𝑤 ∈ 𝐴 iff 𝑓 𝑤 ∈ 𝐵.

Example: 𝐴TM ≤" 𝐸TM

The computable reduction function 𝑓 is 𝑓( 𝑀,𝑤 ) = 𝑀#

Because 𝑀,𝑤 ∈ 𝐴TM iff 𝑀# ∈ 𝐸TM

( 𝑀 accepts 𝑤 iff 𝐿 𝑀# ≠ ∅ )

What is Mapping Reduction's properties?

If 𝐴 ≤m𝐵 and 𝐵 is decidable then so is 𝐴

If 𝐴 ≤m 𝐵 and 𝐴 is undecidable then so is 𝐵

If 𝐴 ≤" 𝐵 and 𝐴 is T-unrecognizable then so is 𝐵

What is the benefits of Mapping Reducibility of 𝐴 to 𝐵?

Translate 𝐴-questions to 𝐵-questions.

-A special type of reducibility

- Useful to prove T-unrecognizability

What is the benefits of General) Reducibility of 𝐴 to 𝐵: Use

Use 𝐵 solver to solve 𝐴.

-May be conceptually simpler

- Useful to prove undecidability

What is the difference between Mapping and General Reducibility?

- 𝐴 is reducible to 𝐴

- 𝐴 may not be mapping reducible to 𝐴.

Is ETM T-recognizable?

No.

Use reduction function

Are both EQTM and EQTM' (complement) T-recognizable?

No.

Why do we use the term "reduce"?

When we reduce 𝐴 to 𝐵, we show how to solve 𝐴 by using 𝐵 and conclude that 𝐴 is no harder than 𝐵. (suggests the ≤" notation)

Possibility 1: We bring 𝐴's difficulty down to 𝐵's difficulty.

Possibility 2: We bring 𝐵's difficulty up to 𝐴's difficulty.

What is the difference between computability theory and complexity theory?

Computability: Is A decidable?

Complexity: Is A decidable with restricted resources? (time/memory/etc)

What is worst-case complexity?

An upper bound for all inputs of length n

What is Big O notation?

𝑓(𝑛) is 𝑂(𝑔(𝑛)) if 𝑓(𝑛) ≤ 𝑐𝑔(𝑛)

for some fixed 𝑐 independent of 𝑛.

What is little o notation?

𝑓(𝑛) is 𝑜(𝑔(𝑛)) if 𝑓(𝑛) ≤ 𝜖𝑔(𝑛)

for all 𝜖 > 0 and large 𝑛.

Does the Number of steps to decide 𝐴 = {a^k b^k | 𝑘 ≥ 0} depends on the model?

Yes.

1-tape TM: 𝑂(𝑛 log 𝑛)

Multi-tape TM: 𝑂(𝑛)

What does the computability theory state?

model independence (Church-Turing Thesis)

Therefore model choice doesn't matter. Mathematically nice.

What does the complexity theory state?

model dependence

But dependence is low (polynomial) for reasonable deterministic models.

What is TIME(t(n))?

TIME 𝑡 𝑛 = {𝐵| some deterministic 1-tape TM 𝑀 decides 𝐵 and 𝑀 runs in time 𝑂(𝑡(𝑛)) }

What is the time complexity of regular language?

O(n)

What is the time complexity of converting a multi-tape to a 1-tape turing machine?

O(t^2(n))

Converting squares the amount of time the multi-tape used.

𝑂(𝑡(𝑛) × 𝑡(𝑛)) = 𝑂(𝑡^2(𝑛)) .

What is the relationship among models?

Two models of computation are polynomially related

if each can simulate the other with a polynomial overhead:

So 𝑡 𝑛 time → 𝑡!(𝑛) time on the other model, for some 𝑘.

What is class P?

P = ⋃k TIME(𝑛^k) = polynomial time decidable languages.

Union of all values of k of Time(n^k).

Is class P invariant for all reasonable deterministic models?

Yes

What is the time complexity of PATH ∈ P?

O(n^4) steps

What is HAMPATH?

the path that goes through every node of G

Is HAMPATH ∈ P ?

Unsolved problem in solving HAMPATH using polynomial time. Can using exponential time.

What is a nondeterministic TM decider?

All branches halt on all inputs

What is NTIME(t(n))?

NTIME(t(n)) = {𝐵| some 1-tape NTM decides 𝐵 and runs in time 𝑂(𝑡(𝑛)) }. All branches halt within t(n) steps.

What is NP?

NP = ⋃k NTIME(𝑛^k) = nondeterministic polynomial time decidable languages.

Invariant for all reasonable nondeterministic models

Corresponds roughly to easily verifiable problems

Is HAMPATH ∈ NP?

Yes, because NTM allows you to check all of the paths on different branches.

Is composites (all non-prime numbers) ∈ NP?

Yes