Bekomp

Question 1

Submission 1:
Do you feel good about Submission 1?

Accepted Answer

Yes

Answer

No

Question 2

1 Parameter counting for travelling salesperson (TSP)
Let us consider the travelling salesperson (TSP) problem for 𝑛 cities.
1.1. How many parameters (pairwise distances) are required to fully specify the TSP problem?

Accepted Answer

$ 𝑛(𝑛 − 1)/2 $ which obeys $ 𝑛^2/4 ≤ 𝑛(𝑛 − 1)/2 ≤ 𝑛^2/2 $ (‘quadratic growth’)

Answer

$𝑛(𝑛 − 1)/2$ which obeys $𝑛/4 ≤ 𝑛(𝑛 − 1)/2 ≤ 𝑛/2$ (‘linear growth’)

Answer

$ 𝑛(𝑛 + 1)/2 $ which obeys $𝑛/2 ≤ 𝑛(𝑛 + 1)/2 ≤ 𝑛 $ (‘linear growth’)

Answer

$ 𝑛(𝑛 + 1)/2 $ which obeys $𝑛^2/2 ≤ 𝑛(𝑛 + 1)/2 ≤ 𝑛^2 $ (‘quadratic growth’)

Question 3

1.2. What is the total number of inequivalent routes once 𝑛 ≥ 3 (and we don’t distinguish between taking routes forward or backwards)?

Accepted Answer

$(𝑛 − 1)!/2$ which obeys $2^𝑛/8 ≤ (𝑛 − 1)!/2 ≤ 𝑛^𝑛/2$ (‘faster than exponential growth’)

Answer

$(𝑛 − 1)^9$ which is polynomial growth behavior

Answer

$(𝑛−1)!/2$ which obeys $(𝑛−1)^2/2 ≤ (𝑛−1)!/2 ≤ 2^𝑛/2$ (‘slower than exponential growth’)

Answer

$2^{𝑛−1}$ which is an exactly exponential growth

Question 4

3 Decimal parity machine
The aim is to design a DFA that computes parity (accept if odd) by processing decimal numbers instead
of binary ones.
3.1. Which of the following four state diagrams describes the correct functionality?

Accepted Answer

c)

Answer

a)

Answer

b)

Answer

d)

Question 5

3.2. Which of the following statements is correct?
Hint: Remember (or look up) how to change the basis of logarithms.

Accepted Answer

$runtime(𝑛) = ⌈log_{10}(𝑛) + 1⌉ ≈ ⌈0.3 × log_2 (𝑛) + 1⌉$ which is faster than the runtime for computing binary parity

Answer

$runtime(𝑛) = ⌈log_{10}(𝑛) + 1⌉ ≈ ⌈3.32 × log_2 (𝑛) + 1⌉$ which is faster than the runtime for computing binary parity

Answer

$runtime(𝑛) = ⌈log_{10}(𝑛) + 1⌉ ≈ ⌈3.32 × log_2 (𝑛) + 1⌉$ which is slower than the runtime for computing binary parity

Answer

$runtime(𝑛) = ⌈log_{10}(𝑛) + 1⌉ ≈ ⌈0.3 × log_2 (𝑛) + 1⌉$ which is slower than the runtime for computing binary parity

Question 6

4 Parity of sums
The aim is to construct a DFA that computes the parity of a sum of bits, i.e. $𝑀(𝑥_1 · · · 𝑥_𝑛) = parity(𝑥_1 + 𝑥_2 + · · · 𝑥_𝑛)$ for any bitstring length $𝑛 ∈ N$.

4.1. Which of the following four state diagrams describes the correct functionality?

Accepted Answer

b)

Answer

a)

Answer

c)

Answer

d)

Question 7

5 State diagram to formal definition of a DFA
Consider the following state diagram of a DFA working over the binary alphabet {0, 1}.
The aim is to convert this state diagram into a formal DFA description (5-tuple) 𝑀 = (𝑄, Σ, 𝛿, 𝑞0, 𝐹). We proceed in two steps.

5.1. Which of the following choices for 𝑄 (set of states), Σ (alphabet), 𝑞0 (starting state) and 𝐹 (accept states) is true:

Accepted Answer

$Q={q,s,x,y,z},Σ={0,1},q_0=y$ and $F={q,y}$

Answer

$Q={q,s,x,y,z},Σ={a,b},q_0=y$ and $F={q,y}$

Answer

$Q={q,y},Σ={0,1},q_0=x$ and $F={q,s,x,y,z}$

Answer

$Q={q,s,x,y,z},Σ={0,1},q_0=y$ and $F={s,x,z}$

Question 8

5.3. Which one of the following bitstrings is accepted by the given DFA?

Accepted Answer

00010110

Answer

01110010

Answer

11100000

Answer

10110010

Question 9

6 Formal definition to state diagram
Consider the DFA defined by the 5-tuple $𝑀 = ({𝑞_0, 𝑞_1, 𝑞_2, 𝑞_3}, {0, 1}, 𝛿, 𝑞_0, {𝑞_3})$, where the transition function 𝛿 acts like

$𝛿(𝑞_0, 0) = 𝑞_1,    𝛿(𝑞_0, 1) = 𝑞_0$,
$𝛿(𝑞_1, 0) = 𝑞_1,    𝛿(𝑞_1, 1) = 𝑞_0$,
$𝛿(𝑞_2, 0) = 𝑞_1,    𝛿(𝑞_2, 1) = 𝑞_0$,
$𝛿(𝑞3, 0) = 𝑞2,    𝛿(𝑞3, 1) = 𝑞0$.

6.1. Which of the following four state diagrams describes the correct functionality?

Accepted Answer

d)

Answer

a)

Answer

b)

Answer

c)

Question 10

6.2. Which one of the following statements is true:

Accepted Answer

This DFA accepts no bitstings at all.

Answer

This DFA accepts all bitstrings ending with a '1'.

Answer

This DFA accepts all bitstrings with a length >= 3.

Answer

This DFA accepts all bitstrings starting with a '1'.

Question 11

7 Reading a DFA
Consider the following state diagram over the alphabet Σ = {a,b,c}.

Which of the following bitstrings is accepted by the underlying DFA?

Accepted Answer

bbbbbaab

Answer

abaccabb

Answer

bcbabcab

Answer

babbaacc

Question 12

8 State diagram to Turing machine I
We consider Turing machines over the alphabet Σ = {0, 1, □, *}, where 0 and 1-symbols are used to write inputs & outputs, □ denotes ‘empty’ tape space and every input must end with a *.
The Turing machine in question is characterized by the following state diagram.

The arrows are labelled by 3-tuples that indicate ‘read’, ‘write’ and ‘move’ (L for left, R for right and S for stop). E.g. (*,1,R) means ‘read *’, ‘write 1’ and ‘move right’. In the following, ‘underline’ denotes the initial and final positions of the TM head. Furthermore, we only consider valid inputs (i.e. only valid symbols, correct syntax, ends with *, etc.). Which of the following statements is correct?

Accepted Answer

This TM counts occurences of the bitstring "01", result is written after the * in unitary encoding (1 -> 1, 11 -> 2, 111 -> 3, ...)
eg. □ 1 0 1 0 1 1 * □ -> □ ... □ * 1 1 □

Answer

This TM counts occurences of the bitstring "010", result is written after the * in unitary encoding (1 -> 1, 11 -> 2, 111 -> 3, ...)
eg. □ 1 0 1 0 1 1 * □ -> □ ... □ * 1 1 □

Answer

This TM mirrors the input, result is written after the *
eg. □ 1 1 1 1 0 0 1 0 0 1 * □ -> □ ... □ * 1 0 0 1 0 0 1 1 1 1 □

Answer

This TM sorts the input such that all 0s are in the front, result is written after the *
eg. □ 1 1 1 0 0 0 0 1 0 1 1 * □ -> □ ... □ * 0 0 0 0 0 1 1 1 1 1□

Question 13

9 State diagram to Turing machine II
We consider Turing machines over the alphabet Σ = {0, 1, □, *}, where 0 and 1-symbols are used to write inputs & outputs, □ denotes ‘empty’ tape space and every input must end with a *.
The Turing machine in question is characterized by the following state diagram.

The arrows are labelled by 3-tuples that indicate ‘read’, ‘write’ and ‘move’ (L for left, R for right and S for stop). E.g. (*,1,R) means ‘read *’, ‘write 1’ and ‘move right’. In the following, ‘underline’ denotes the initial and final positions of the TM head. Furthermore, we only consider valid inputs (i.e. only valid symbols, correct syntax, ends with *, etc.). Which of the following statements is correct?

Accepted Answer

This TM sorts the input such that all 0s are in the front, result is written after the *
eg. □ 1 1 1 0 0 0 0 1 0 1 1 * □ -> □ ... □ * 0 0 0 0 0 1 1 1 1 1 1 □

Answer

This TM counts occurences of the bitstring "01", result is written after the * in unitary encoding (1 -> 1, 11 -> 2, 111 -> 3, ...)
eg. □ 1 0 1 0 1 1 * □ -> □ ... □ * 1 1 □

Answer

This TM counts occurences of the bitstring "010", result is written after the * in unitary encoding (1 -> 1, 11 -> 2, 111 -> 3, ...)
eg. □ 1 0 1 0 1 1 * □ -> □ ... □ * 1 1 □

Answer

This TM mirrors the input, result is written after the *
eg. □ 1 1 1 1 0 0 1 0 0 1 * □ -> □ ... □ * 1 0 0 1 0 0 1 1 1 1 □

Question 14

Submission 2:
Do you feel good about Submission 2?

Accepted Answer

Yes

Answer

No

Question 15

2.4 The illustrations in Figure 1 show how to combine two DFAs – one (𝑀𝐴) for regular language 𝐴 and one (𝑀𝐵) for regular language 𝐵 – to get another DFA that accepts a certain combination. Which of the following combinations is true?

Accepted Answer

combination c) shows union, combination a) shows concatenation, combination b) shows star

Answer

combination a) shows union, combination b) shows concatenation, combination c) shows star

Answer

combination c) shows union, combination b) shows concatenation, combination a) shows star

Answer

combination b) shows union, combination a) shows concatenation, combination c) shows star

Question 16

3 Regular operations II
3.1. The negation operation $ \overline {A}={x∈Σ* : x∉A} $ is a regular operation, because

Accepted Answer

we can convert a DFA accepting A into a DFA accepting $ \overline{A} $by changing the set of accepting states,

Answer

we can convert a DFA accepting A into a DFA accepting $ \overline{A} $ by changing the starting state,

Answer

we can convert a DFA accepting A into a DFA accepting $ \overline{A} $ by reversing all arrows in the transition function,

Answer

this is a trick question. Negation is not a regular operation.

Question 17

3.2. The intersection operation $ A∩B={x∈Σ∗:x∈A and x∈B} $ is a regular operation, because

Accepted Answer

we can negate, then take the union and finally negate again to effectively compute it: $ A∩B=\overline{\overline{A}∪\overline{B}} $

Answer

we can first concatenate 𝐴 with 𝐵 and subsequently subselect to effectively compute it: $ A∩B=N(AB) $, where 𝑁 is a simple DFA that compares individual symbols

Answer

we can first take the union and subsequently invert to effectively compute it: $A∩B=\overline{A∪B} $

Answer

this is a trick question. Intersection is not a regular operation

Question 18

3. The reverse operation $A^R={xR:x∈A}$, where $x^R=x_{n−1}⋯x_0$ is the reverse of $x=x_0⋯x_{n−1}$, is a regular operation, because

Accepted Answer

we can convert a DFA accepting 𝐴 into a DFA accepting $𝐴^R$ by reversing all arrows in the transition function and swapping starting and accept states;

Answer

we can convert a DFA accepting 𝐴 into a DFA accepting $𝐴^R$ by only changing the set of accepting states;

Answer

we can convert a DFA accepting 𝐴 into a DFA accepting $𝐴^R$ by only reversing arrows in the transition function;

Answer

this is a trick question. Reverse is not a regular operation.

Question 19

4.2. Which of the following implications is correct:

Accepted Answer

even PALINDROME and odd PALINDROME are both decidable, but not regular.

Answer

even PALINDROME is decidable, while odd PALINDROME is only semi-decidable;

Answer

odd PALINDROME is decidable, while even PALINDROME is only semi-decidable;

Answer

even PALINDROME and odd PALINDROME are semi-decidable, but not decidable;

Question 20

5 Turing Machines
Let two languages A and B be defined as follows:
$A = {0^k1^k ∈ {0, 1}* : k ∈ ℕ}$,
$B = {1^k ∈ {0, 1}* : k ∈ ℕ}$
The TM state diagrams in picture a) and b) are connected to the languages above for a fixed k. Which of the following assertions is fully correct:

Accepted Answer

"a)" accepts A while "b)" accepts $A^R$

Answer

"b)" accepts $BA^R$

Answer

"a)" accepts A and its reverse $A^R$ while "b)" accepts B and its reverse $B^R$

Answer

none of the above

Question 21

6.4. Which of the following inclusions is true:

Accepted Answer

regular⊆decidable⊆semidecidable;

Answer

regular⊆decidable, but semidecidable languages are incomparable;

Answer

regular⊆semidecidable⊆decidable.

Answer

decidable⊆semidecidable, but regular languages are incomparable;

Question 22

7 Complements of (semi-)decidable languages
Let $ A⊆Σ* $ be a language and $ \overline{A} \text{ its complement, i.e. } \overline{A}={x∈Σ∗:x∉A}$.
7.1. Which of the following statements is true:

Accepted Answer

𝐴 is decidable if and only if 𝐴 and Ā are both semidecidable (both directions are always true);

Answer

If 𝐴 is decidable, then both 𝐴 and Ā are semi-decidable; but the converse direction is false;

Answer

If 𝐴 and Ā are both semi-decidable, then 𝐴 must be decidable; but the converse direction is false;

Answer

there is no obvious connection in general (either direction may be false).

Question 23

8 Combinations of languages with the star operation
Fix an alphabet Σ and let 𝐴 ⊆ Σ* be a language. The operation star is defined as

$𝐴* = {𝜀} ∪ 𝐴 ∪ 𝐴𝐴 ∪ 𝐴𝐴𝐴 ∪ · · · $,

where 𝐴𝐴 = {𝑥𝑦 : 𝑥 ∈ 𝐴 and 𝑦 ∈ 𝐴} denotes concatenation of 𝐴 with itself and 𝐴𝐴𝐴,
etc. is defined accordingly.
8.1. Mark the most general statement that is still correct:

Accepted Answer

if 𝐴 is a semi-decidable language, then 𝐴* is also semi-decidable;

Answer

if 𝐴 is a regular language, then 𝐴* is also regular;

Answer

if 𝐴 is a decidable language, then 𝐴* is also decidable;

Answer

none of the above implications is true in general.

Question 24

9 The halting problem
Define the language HALT= { $\lfloor (M,w) \rfloor :\text{M is a TM that halts on input w}$}⊂{0,1}*, where M describes a Turing machine, w∈{0,1}* and $ \lfloor (⟨M,w⟩)\rfloor $ is a suitable (and fixed) binary encoding of the two.

1. Only one of the following statements about HALT
 is false. Which one is it?

Accepted Answer

$HALT$ is not semi-decidable;

Answer

$HALT$ is not decidable;

Answer

the complement $\overline{HALT}$ is not decidable;

Answer

the complement $\overline{HALT}$ is not semi-decidable.

Question 25

10 Variants of Turing Machines I: stationary tape head
The aim of this exercise is to show if a Turing Machine whose head may remain stationary can be simulated by a standard TM whose head must move right/left at each step.
10.1. The key idea is to

Accepted Answer

simulate a stationary tape head (𝑆) by executing two steps: one where the head moves right and one where the head moves left;

Answer

duplicate all input symbols multiple times (towards the left and the right), such that it takes (at least) two left or right steps to move to the next box symbol;

Answer

introduce a two-track tape (see Exercise 13) and zig-zagging it whenever we want to stay stationary;

Answer

this is a trick question. TMs with stationary tape heads cannot be simulated by ordinary TMs at all.

Question 26

10.2. The worst-case overhead in runtime (number of steps) is

Accepted Answer

at most a constant factor of two;

Answer

more than a factor of two, but at most proportional to the maximum number $ℓ_{max}$ of occupied boxes;

Answer

more than proportional to the maximum number of occupied boxes $ℓ_{max}$ but at most proportional to a polynomial in $ℓ_{max}$’

Answer

this is a trick question. TMs with stationary tape heads cannot be simulated by ordinary TMs at all.

Question 27

10.3. The worst-case overhead in the required number of states is

Accepted Answer

at most two times the original number of states;

Answer

more than two times the number of original states |𝑄|, but at most exponentially in |𝑄|;

Answer

the number of states required may actually depend on the size of the input 𝑥 to be processed.

Answer

this is a trick question. TMs with stationary tape heads cannot be simulated by ordinary TMs at all.

Question 28

11 Variants of Turing Machines II: binary symbol alphabet
The aim of this exercise is to show if a Turing Machine with tape alphabet Σ ∪ {□} can be simulated by a binary TM with tape alphabet Γ = {0, 1,□}.

11.1. The most promising key idea is to

Accepted Answer

encode input symbols 𝜎 ∈ Σ as bitstrings ⌞𝜎⌟; subsequently, we use additional internal states to ‘recognize’ these symbols which allows us to effectively execute the original transition function;

Answer

write a small pre-converter that encodes every input 𝑥 ∈ Σ* into a binary input;
subsequently, we construct a new TM for the actual (binary) computation;

Answer

we can use tape movements (left and right) to effectively encode and process alphabet symbols Σ (similar to Morse code);

Answer

this is a trick question. TMs with tape alphabet Σ ∪ {□} cannot be simulated by binary TMs at all.

Question 29

11.2. The worst-case overhead in runtime (number of steps) is

Accepted Answer

more than factor of two, but at most logarithmic in the size of the input alphabet;

Answer

at most a constant factor of two;

Answer

more than logarithmic in the size of the input alphabet, but at most polynomial;

Answer

this is a trick question. TMs with tape alphabet Σ ∪ {□} cannot be simulated by binary TMs at all.

Question 30

11.3. The worst-case overhead in the required number of states is

Accepted Answer

more than two times the number of states, but at most proportional to |𝑄||Σ|;

Answer

at most two times the original number of states |𝑄|;

Answer

the number of states grows faster than $|𝑄|^2|Σ|$, but is at most proportional to $|𝑄|^{|Σ|}$;

Answer

this is a trick question. TMs with tape alphabet Σ ∪ {□} cannot be simulated by binary TMs at all.

Question 31

12 Variants of Turing Machines 3: one-way infinite tape
The aim of this exercise is to show if a TM with a one-way infinite tape can efficiently simulate another TM that has an infinitely long tape in both directions.

12.1. The most promising key idea is

Accepted Answer

to bend the two-way infinite tape somewhere in the middle and introduce a new tape alphabet of size $|Γ|^2$ to represent two symbols within one box;

Answer

to introduce a tape cutoff somewhere in the middle; start with the positive tape part and append (concatenate) the negative tape part to the right of it;

Answer

to introduce a tape cutoff somewhere in the middle; symbols towards the right of the cut are encoded at even tape squares while symbols towards the left are encoded at odd tape positions;

Answer

this is a trick question. The objective is impossible, because one-way infinite TMs have infinitely fewer tape space than a two-way infinite TM.

Question 32

12.2. The worst-case overhead in runtime (number of steps) is

Accepted Answer

at most a constant factor of four;

Answer

at least a factor of four, but at most proportional to the maximum number $ℓ_{max}$ of occupied boxes;

Answer

at least proportional to the maximum number of occupied boxes $ℓ_{max}$ but at most proportional to a polynomial in $ℓ_{max}$’

Answer

this is a trick question; see above.

Question 33

12.3. The worst-case overhead in the required number of states is

Accepted Answer

at most two times the original number of states;

Answer

more than the number of original states |𝑄|, but at most exponentially in |𝑄|;

Answer

the number of states does not change at all;

Answer

this is a trick question; see above.

Question 34

Submission 3:
Do you feel good about Submission 3?

Accepted Answer

Yes

Answer

No

Question 35

1.2. What is the asymptotic scaling of the following function: $w(n)=n^22^n$

Accepted Answer

$w(n)=2^{O(n)}$

Answer

$w(n)=O(n^2)$

Answer

$w(n)=O(2^n)$

Answer

$w(n)=2^{O(n^2)}$

Question 36

2 Properties of the big-O notation
2.1. Only one of the following reformulations is correct. Which one is it:

Accepted Answer

$2^{O(log(n))}=n^c$ for some $c≥1$

Answer

$O(3^n)=O(9^n)$

Answer

$2^{O(log^k(n))}=(2^{O(log(n))})^c$ for some $c≥1$

Answer

this is a trick question; none of these formulas are correct

Question 37

2.2. Three of the four following relations are true for any 𝑘 ∈ N. Mark the one which is wrong:

Accepted Answer

$2^{O(n^k)}=O(2^{n^k})$

Answer

$log(O(n^k))=O(log(n))$

Answer

$(O(n^k))^2=O(n^{2k})$

Answer

$log(2^{O(n^k)})=O(n^k)$

Question 38

3 Scaling discrepancies between logarithms, polynomials and exponentials
3.1. The observation that exponential growth eventually outweighs any type of polynomial growth is central to computational complexity theory. It may be viewed as a consequence of the following big-O relation:

$𝑛^𝑘 = 𝑂(2^𝑛)$ for any polynomial degree 𝑘 ∈ N.            (1)

‘Prove’ this relation by selecting the correct argument:

Accepted Answer

For ‘small’ values of 𝑛, polynomials can actually be larger than exponentials. But choosing $𝑛_0$ to be the smallest natural number that obeys $𝑛_0/ log_2(𝑛_0) ≥ 𝑘$ ensures $2^𝑛 ≥ 𝑛^𝑘$ for all $𝑛 ≥ 𝑛0$

Answer

The claim follows from a stronger statement: $𝑛^𝑘 ≤ 2^𝑛$ for all 𝑛 ∈ N, because exponentials are always larger than polynomials.

Answer

For ‘small’ values of 𝑛, polynomials can actually be larger than exponentials. But choosing $𝑛_0$ to be the smallest natural number that obeys $𝑛_0 ≥ 𝑘$ ensures $2^𝑛 ≥ 𝑛^𝑘$ for all $𝑛 ≥ 𝑛_0$.

Answer

For ‘small’ values of 𝑛, polynomials can actually be larger than exponentials. But choosing $𝑛_0$ to be the smallest natural number that obeys $𝑛_0 ≥ 𝑘*log_2(𝑘)$ ensures $2^𝑛 ≥ 𝑛^𝑘$ for all $𝑛 ≥ 𝑛0$.

Question 39

3.2. When analyzing runtimes of algorithms, we also often ignore (poly-)logarithmic factors. This is because polynomial growth outweighs logarithmic growth. This may be viewed as a consequence of the following big-O notation:

$log^{k}_{2}(n)=O(n)$ for all k∈N.

‘Prove’ this relation by selecting the correct argument:

Accepted Answer

We can use a change of variables trick. Writing $n=2^m$ for some m∈R, this claim follows from Eq.(1).

Answer

The claim follows from a stronger statement: $log_2(n)^k ≤ n$ for all n∈N, because logarithms are always sublinear functions.

Answer

For 'small' values of n, powers of logarithms can actually be larger than f(n)=n. But choosing $n_0$ to be the smallest natural number that obeys $n_0≥k^{1/k}$ ensures $n≥log^{k}_{2}(n)$ for all $n ≥ n_0$.

Answer

We can use a change of variables trick. Writing $n=m^k$ for some m∈R, this claim follows from Eq.(1).

Question 40

4 High-level comparison of algorithm runtimes
Suppose that we have two algorithms that compute the same Boolean function 𝑓 : {0, 1}* → {0, 1}. Suppose that the first algorithm runs in time $𝑎(𝑛) = 1.01^𝑛$ and the second algorithm runs in $𝑏(𝑛) = 100 000 × 𝑛^2$, where 𝑛 denotes the size of the binary input 𝑥.

4.1. Which of the following runtime comparisons is correct:

Accepted Answer

𝑏(𝑛) = 𝑂(𝑎(𝑛));

Answer

𝑎(𝑛) = 𝑂(𝑏(𝑛));

Answer

𝑎(𝑛) = 𝑂(𝑏(𝑛)) and 𝑏(𝑛) = 𝑂(𝑎(𝑛));

Answer

the two runtimes are incomparable;

Question 41

4.2. This asymptotic scaling kicks in once

Accepted Answer

𝑛 ≥ 2749;

Answer

𝑛 ≥ 27;

Answer

𝑛 ≥ 274;

Answer

𝑛 ≥ 27493.

Question 42

5 Runtime and space complexity of a simple TM
Let 𝑀 = ({$𝑞_0, 𝑞_1$}, {0,1}, {0,1,□}, 𝛿, $𝑞_0$, $𝑞_1$}) be the TM whose transition function is specified by 𝛿($𝑞_0$, 0) = ($𝑞_0$, 0,𝑅) and 𝛿($𝑞_0$,1) = ($𝑞_1$,1,𝑅), respectively. Other transitions cannot occur. The running time measures the number of computational steps, while the space complexity measures the number of TM tape squares that are being used.

5.1. Which of the following statements is correct:

Accepted Answer

the worst-case runtime of 𝑀 scales linearly in input length;

Answer

the worst-case runtime of 𝑀 is independent of input length;

Answer

the worst-case runtime of 𝑀 scales quadratically in input length;

Answer

the worst-case runtime of 𝑀 scales exponentially in input length.

Question 43

5.2. Space complexity measures the maximum number of TM tape squares that are being used. Which of the following statements is correct:

Accepted Answer

the worst-case space complexity of 𝑀 scales linearly in input length;

Answer

the worst-case space complexity of 𝑀 is independent of input length;

Answer

the worst-case space complexity of 𝑀 scales quadratically in input length;

Answer

the worst-case space complexity of 𝑀 scales exponentially in input length.

Question 44

6 The problem class P
6.1. Informally speaking, the problem class P encompasses problems that are ‘easy’ to solve with a TM. The P is an abbreviation for

Accepted Answer

Polynomial runtime;

Answer

Provably efficient;

Answer

Probably efficient;

Answer

Polynomial space requirements.

Question 45

2. More formally, a language 𝐴 ⊆ {0, 1}* is in P if

Accepted Answer

there exists a TM 𝑀 that accepts 𝑥 ∈ 𝐴 in a runtime that is (at most) polynomial in input size |𝑥|, moreover 𝑀 does not accept any string that is not in the language (𝑥 ∉ 𝐴);

Answer

there exists a TM 𝑀 that accepts 𝑥 ∈ 𝐴 in a runtime that is (at most) polynomial in input size |𝑥|, but we don’t make any statements about strings not in the language (𝑥 ∉ 𝐴);

Answer

there exists a TM 𝑀 that accepts 𝑥 ∈ 𝐴 and requires a number of tape squares that is (at most) polynomial in input size |𝑥|, but we don’t make any statements about strings not in the language (𝑥 ∉ 𝐴);

Answer

there exists a TM 𝑀 that accepts 𝑥 ∈ 𝐴 and requires a number of tape squares that is (at most) polynomial in input size |𝑥|, moreover 𝑀 does not accept any string that is not in the language (𝑥 ∉ 𝐴);

Question 46

7 The problem class NP
7.1. Informally speaking, the problem class NP encompasses problems that are ‘efficient’ to verify. The name NP is an abbreviation for

Accepted Answer

Nondeterministic Polynomial runtime

Answer

Not Provably efficient;

Answer

Not Polynomial runtime;

Answer

No Polynomial space requirements

Question 47

7.2. More formally, a language 𝐴 ⊆ {0, 1}* is in NP if

Accepted Answer

There is a TM 𝑀 (the ‘verification procedure’) such that for every 𝑥 ∈ 𝐴 there is another string 𝑦 ∈ {0, 1}* (the ‘verifier’) such that 𝑀(𝑥, 𝑦) = accept. Moreover, both the length |𝑦| of 𝑦 and the runtime of 𝑀 must be polynomial in |𝑥|. Moreover, 𝑥 ∉ 𝐴, must imply 𝑀(𝑥, 𝑦) = reject for all possible verifiers 𝑦 (‘no false positives’).

Answer

There is a TM 𝑀 (the ‘verification procedure’) such that for every 𝑥 ∈ 𝐴 there is another string 𝑦 ∈ {0, 1}* (the ‘verifier’) such that 𝑀(𝑥, 𝑦) = accept. There are no further restrictions on 𝑀 and 𝑦.

Answer

There is a TM 𝑀 (the ‘verification procedure’) such that for every 𝑥 ∈ 𝐴 there is another string 𝑦 ∈ {0, 1}* (the ‘verifier’) such that 𝑀(𝑥, 𝑦) = accept. There are no further restrictions on 𝑀 and 𝑦. It is, however, important that 𝑥 ∉ 𝐴 implies 𝑀(𝑥, 𝑦) = reject for all possible verifiers 𝑦 (‘no false positives’).

Answer

There is a TM 𝑀 (the ‘verification procedure’) such that for every 𝑥 ∈ 𝐴 there is another string 𝑦 ∈ {0, 1}* (the ‘verifier’) such that 𝑀(𝑥, 𝑦) = accept. Moreover, the runtime of 𝑀 must be polynomial in |𝑥|, but the length of 𝑦 can be arbitrary. It is, however, important that 𝑥 ∉ 𝐴 implies 𝑀(𝑥, 𝑦) = reject for all possible verifiers 𝑦 (‘no false positives’).

Question 48

8 The problem class EXP
8.1. Informally speaking, the problem class EXP encompasses problem that are computable, but in a truly expensive fashion. The name EXP is an abbreviation for

Accepted Answer

EXPonential runtime;

Answer

not provably efficient in EXPectation (bad worst-case runtime);

Answer

EXPonential space requirements;

Answer

EXPected bankruptcy because of memory/time requirements.

Question 49

8.2. More formally, a language 𝐴 ⊆ {0, 1}* is in EXP if

Accepted Answer

There exists a TM 𝑀 that accepts 𝑥 ∈ 𝐴 in a runtime that is (at most) exponential in input size |𝑥|. Moreover 𝑀 does not accept any string that is not in the language (𝑥 ∉ 𝐴);

Answer

There exists a TM 𝑀 that accepts 𝑥 ∈ 𝐴 in a runtime that is (at most) exponential in input size |𝑥|. But we don’t make any statements about strings not in the language (𝑥 ∉ 𝐴);

Answer

There exists a TM 𝑀 that accepts 𝑥 ∈ 𝐴 and requires a number of tape squares that is (at most) exponential in input size |𝑥|. But we don’t make any statements about strings not in the language (𝑥 ∉ 𝐴);

Answer

There exists a TM 𝑀 that accepts 𝑥 ∈ 𝐴 and requires a number of tape squares that is (at most) exponential in input size |𝑥|. Moreover 𝑀 does not accept any string that is not in the language (𝑥 ∉ 𝐴).

Question 50

8.3. The class EXP contains an enormous number of problems. Which of the following two statements is correct:

Accepted Answer

There are languages 𝐴 ⊆ {0, 1}* that are not contained in EXP.

Answer

Every language 𝐴 ⊆ {0, 1}* is contained in EXP.

Question 51

9.3. Only one of the following statements is false. Which one is it:

Accepted Answer

P ≠ EXP would imply P ≠ NP;

Answer

proving P ≠ NP would turn you into a millionaire;

Answer

P ≠ NP would imply P ≠ EXP;

Answer

NP ≠ EXP would imply P ≠ EXP.

Question 52

9.4. At most one of the following statements has been proven to be true. Which one is it:

Accepted Answer

P ≠ EXP

Answer

P ≠ NP

Answer

NP ≠ EXP

Answer

none of the above

Question 53

11 The satisfiability problem
Let $ \phi(x_0,…,x_{n−1}) $∈{0,1} be a Boolean formula in n truth variables $x_0,…,x_{n−1}$∈{0,1}. A decision version of the Boolean satisfiability problem is
SAT={$\lfloor \phi \rfloor $: there is an assignment $x_0,…,x_{n−1}$ such that $ \phi (x_0,…,x_{n−1})$=1}.

Accepted Answer

SAT is in NP, but the explanation in (b) is not complete yet. It is also important to point out that $ \lfloor \phi \rfloor ∉ SAT $ necessarily implies that no satisfiable assignment can exist (or that the encoding is wrong). I.e. $ \phi (x_0,…,x_{n−1})=0$ for all $x_0,…,x_{n−1}$, so there is no proof of correctness that leads us to accept such formulas.

Answer

SAT is in P, because it is possible to evaluate every Boolean formula in a runtime that is polynomial in input size |$ \lfloor \phi \rfloor $|.

Answer

SAT is in NP, because if one had access to a satisfiable assignment $x^{♯}_{0},…,x^{♯}_{n−1} $∈{0,1}, satisfiability can be efficiently verified by computing ϕ(x♯0,…,x♯n−1)=1. I.e.\ the TM M computes the Boolean formula $\phi$ and $y=\lfloor (x^{♯}_{0},…,x^{♯}_{n−1}) \rfloor $ is the proof of correctness. Both the runtime of M and the length of |y| scale polynomially in input size.

Answer

SAT is in NP, but the explanations from (b) and (c) are still not complete yet. It is also important to note that it is possible to compute $ \phi (x_0,…,x_{n−1})$ for all possible input values in exponential runtime. This is achieved by iteratively computing $ \phi(x_0,…,x_{n−1})$ for all $2^n$ possible choices of $x_0,…,x_{n−1}$∈{0,1}*. Such a complete check is necessary to unambiguously determine whether $ \phi $ is satisfiable or not. And this is essential to conclude SAT is in NP.

Question 54

12 A variant of TSP is in NP
12.1. Recall that the traveling salesperson problem (TSP) asks for evaluating the shortest route that visits a total of 𝑛 cities exactly once. It is completely specified by a pairwise distance table 𝐷 ∈ $R^{𝑛×𝑛}$. There are many ways to convert TSP into a decision problem. But only one of the following choices is in NP. Which one is it:

Accepted Answer

TSP3 = {⌞(𝐷, 𝑘)⌟ : 𝐷 as above and there exists a route that requires at most 𝑘 kilometers};

Answer

TSP1 = {⌞(𝐷, 𝑟)⌟ : 𝐷 is a pairwise distance table and 𝑟 is a shortest route};

Answer

TSP2 = {⌞(𝐷, 𝑘)⌟ : 𝐷 is a pairwise distance table and 𝑘 is the shortest km count};

Answer

TSP4 = {⌞(𝐷, 𝑘)⌟ : 𝐷 as above and all routes require at most 𝑘 kilometers};

Question 55

Submission 4:
Do you feel good about Submission 4?

Accepted Answer

Yes

Answer

No

Question 56

1 Bringing Boolean formulas into CNF
Here, we consider certain Boolean functions $\text{f:{0,1}}^3$ → {0,1} on 3 bits.
1.1. What is the CNF for the language Palindrome (i.e. reading forward is the same as reading backwards)?

Accepted Answer

$φ(x,y,z)=(x∨y∨\overline{z})∧(x∨\overline{y}∨\overline{z})∧(\overline{x}∨y∨z)∧(\overline{x}∨\overline{y}∨z)$

Answer

$φ(x,y,z)=(x∨\overline{y}∨z)∧(x∨\overline{y}∨\overline{z})∧(\overline{x}∨y∨\overline{z})∧(\overline{x}∨\overline{y}∨z)$

Answer

$φ(x,y,z)=(x∨y∨z)∧(x∨\overline{y}∨z)∧(\overline{x}∨y∨z)∧(\overline{x}∨\overline{y}∨z)$

Answer

$φ(x,y,z)=(x∧y∧z)∨(x∧\overline{y}∧z)∨(\overline{x}∧y∧\overline{z})∨(\overline{x}∧\overline{y}∧\overline{z})$

Question 57

1.2. What is the CNF formula for the language Parity (i.e. it ends with 1)?

Accepted Answer

$φ(x,y,z)=(x∨y∨z)∧(x∨\overline{y}∨z)∧(\overline{x}∨y∨z)∧(\overline{x}∨\overline{y}∨z)$

Answer

$φ(x,y,z)=(x∨\overline{y}∨z)∧(x∨\overline{y}∨\overline{z})∧(\overline{x}∨y∨\overline{z})∧(\overline{x}∨\overline{y}∨z)$

Answer

$φ(x,y,z)=(x∨y∨\overline{z})∧(x∨\overline{y}∨\overline{z})∧(\overline{x}∨y∨z)∧(\overline{x}∨\overline{y}∨z)$

Answer

$φ(x,y,z)=(x∧y∧z)∨(x∧\overline{y}∧z)∨(\overline{x}∧y∧z)∨(\overline{x}∧\overline{y}∧z)$

Question 58

1.3. What is the CNF formula for the language Up (i.e. all 1's are to the right)?

Accepted Answer

$ φ(x,y,z)=(x∨\overline{y}∨z)∧(\overline{x}∨y∨z)∧(\overline{x}∨y∨\overline{z})∧(\overline{x}∨\overline{y}∨z) $

Answer

$ φ(x,y,z)=(x∨y∨\overline{z})∧(x∨\overline{y}∨\overline{z})∧(\overline{x}∨y∨z)∧(\overline{x}∨\overline{y}∨z) $

Answer

$ φ(x,y,z)=(x∨y∨z)∧(x∨\overline{y}∨z)∧(\overline{x}∨y∨z)∧(\overline{x}∨\overline{y}∨z) $

Answer

$ φ(x,y,z)=(x∨y∨z)∧(x∨\overline{y}∨\overline{z})∧(\overline{x}∨y∨\overline{z})∧(\overline{x}∨\overline{y}∨z) $

Question 59

1.4. What is the CNF for the language SumOfParity (i.e. the sum of all digits is odd)?

Accepted Answer

$ φ(x,y,z)=(x∨y∨z)∧(x∨\overline{y}∨\overline{z})∧(\overline{x}∨y∨\overline{z})∧(\overline{x}∨\overline{y}∨z) $

Answer

$ φ(x,y,z)=(\overline{x} ∧ \overline{y} ∧ z)∨(x ∧ \overline{y} ∧ \overline{z}) ∨ (\overline{x} ∧ y ∧ \overline{z}) ∨ (x ∧ y ∧ z) $

Answer

$ φ(x,y,z)=(x∨\overline{y}∨z)∧(x∨\overline{y}∨\overline{z})∧(\overline{x}∨y∨\overline{z})∧(\overline{x}∨\overline{y}∨z) $

Answer

$ φ(x,y,z)=(x∨y∨z)∧(x∨\overline{y}∨z)∧(\overline{x}∨y∨z)∧(\overline{x}∨\overline{y}∨z) $

Question 60

2 Reducing k-CNFs to 3-CNFs
Consider the following simple clause of size 6: $φ(x)=(x_0∨x_1∨x_2∨x_3∨x_4∨x_5)$. Which of the following formulas in $x=x_0x_1x_2x_3x_4x_5$ and $y=y_0y_1y_2$ is a functionally equivalent 3-CNF:
Hint: rather than comparing functionalities, do the transformation from 6-clause to 3-CNF yourself and check which one you obtain.

Accepted Answer

$ψ(x,y)=(x_0 ∨ x_1 ∨ y_1) ∧ (\overline{y}_1 ∨ x_2 ∨ y_0) ∧ (\overline{y}_0 ∨ x_3 ∨ y_2) ∧ (\overline{y}_2 ∨ x_4 ∨ x_5)$

Answer

$ ψ(x,y)=(x_0 ∨ x_1 ∨ y_0) ∧ (\overline{y}_1 ∨ x_2 ∨ y_1) ∧ (\overline{y}_0 ∨ x_3 ∨ y_2) ∧ (\overline{y}_2 ∨ x_4 ∨ x_5) $

Answer

$ ψ(x,y)=(x_0 ∨ x_1 ∨ y_2) ∧ (\overline{y}_1 ∨ x_2 ∨ y_0) ∧ (\overline{y}_0 ∨ x_3 ∨ y_0) ∧ (\overline{y}_2 ∨ x_4 ∨ x_5) $

Answer

none of the above is correct

Question 61

3 SAT or UNSAT
Which of the following boolean formulas are satisfiable (i.e. there exists an assignment λ for the variables such that φ(λ)=1): Attention: There can be multiple correct answers, select all of them.

Accepted Answer

$φ(x,y,z)=(z∨y)∧(z∨x)∧(z∨\overline{x})∧(\overline{z}∨x)$

Accepted Answer

$φ(x,y,z)=(x∨y∨\overline{z})∧(x∨\overline{y}∨\overline{z})∧(\overline{x}∨y∨z)∧(\overline{x}∨\overline{y}∨z)$

Accepted Answer

$φ(x,y)=(\overline{x}∨\overline{y})∧x∧\overline{y}$

Answer

$ φ(x,y)=(\overline{x}∨\overline{y})∧x∧y $

Question 62

4 Solving 3-SAT unveils satisfiying assignments
Suppose you had access to an algorithm that could reliably decide

3-SAT = {$ \lfloor \phi \rfloor $:φ is 3-CNF that is satisfiable}⊆{0,1}∗.

Now, you are given a 3-SAT formula φ($x_0,…,x_{n−1}$) in n variables that is satisfiable (φ∈3-SAT).
4.1. What is the smallest number N of algorithm invocations (the so-called `query complexity') that is required to also identify a satisfiable assignment, i.e.\ bits $x^{♯}_{0},…,x^{♯}_{n−1}$∈{0,1} such that $φ(x^{♯}_{0},…,x^{♯}_{n−1})=1$:

Accepted Answer

𝑁 = 2n

Answer

𝑁 = 4

Answer

$𝑁 = 2^n $

Answer

this is a tricky question; being able to decide 3-SAT has nothing to do with actually finding satisfying assignments

Question 63

5 The Cook-Levin Theorem
5.1. Which of the following phrases describes the Cook-Levin theorem informally:

Accepted Answer

We can map any NP-problem to an instance of 3-SAT, moreover the overhead is (at most) polynomial;

Answer

We can map 3-SAT to an instance of any NP problem;

Answer

We can map any NP-problem to an instance of 3-SAT;

Answer

We can map 3-SAT to an instance of any NP problem, moreover the overhead is (at most) polynomial.

Question 64

5.2. Let 𝐴 ⊆ {0, 1}* be a NP-language with verifier 𝑀 and let
3-SAT = {$ \lfloor \phi \rfloor $:φ is 3-CNF that is satisfiable}.
Which of the following phrases describes the Cook-Levin theorem formally:

Accepted Answer

Same as in (b), but the size of φ also depends polynomially on input length |𝑥|.

Answer

For every 3-CNF φ, there exists an element 𝑥 ∈ 𝐴 such that 𝑥 ∈ 𝐴 if and only if φ ∈ 3-SAT;

Answer

For each 𝑥 ∈ {0, 1}* , there is a 3-CNF φ such that 𝑥 ∈ 𝐴 if and only if φ ∈ 3-SAT. The function φ only depends on 𝑥 (input) and 𝑀 (verifier);

Answer

Same as in (a), but the size of φ also depends polynomially on input length |𝑥|;

Bekomp

Create a free account to finish this quiz

Information

Feedback

What do you think of the new look?