DM553 / MM850 - Computability and Complexity

This exercise concerns theorem 3.21 which states that a language Turing-recognizable iff some enumerator enumerates it. We are to consider a wrong simplification of the proof in one direction; given TM, construct enumerator printing its language. Let \(s_1, s_2, \dots\) be all strings of \(\Sigma^*\)

• For \(i = 1,2,\dots\)
  • Run \(M\) on \(s_i\) (original proof of 3.21: run \(i\) steps on each of \(s_1, s_2, \dots, s_i\))
  • If accept, print \(s_i\)

Answer: the problem is that we don’t know that \(M\) will necessarily halt (only a recognizer). Thus, our constructed enumerator may get stuck if \(M\) loops.

Show: a language decidable iff there is an enumerator enumerating it in standard string order. Main point: consider when / why decidability is important here.

Answer:

• Decidable if enumerable in order
  • We wish to construct a TM that will decide if an input string \(w\) is in the language of the enumerator
  • Inspired by theorem 3.21, let the enumerator print out all strings of the language in standard string order
  • Simulate this enumerator and every time it says to print a string \(s_i\), compare this to \(w\). Accept if equal.
  • We also need to reject all strings not in the language. Due to knowing an ordering on the strings, we can tell if the strings output by the enumerator are suddenly “past” the input string. In this case (\(w \prec s_i\)), reject
• Enumerable in order if decidable: just like original proof. Enumerate all strings of \(\Sigma^*\) in order, run machine on each and print if accept.

Write-once TM: a TM which can only change symbol on each position on tape at most once. Show: this model of TM can do the same as a normal Turing machine can.

Hint: start out by considering write-twice TM and using a lot of tape.

Answer: let’s start with a way to simulate a normal TM in a write-twice TM. Idea: every time we would like to write to a cell for the second time, mark it instead. Then add a delimiter to the end of current tape contents, copy everything up to the mark, then write the replaced symbol and finally the rest of the old contents. This way, we can end up copying the entire content of the tape per write—but it works.

Now for the write-once version, we need to implement the marking without writing twice. We can do this by using two fields per element instead of one such that each copied symbol a is copied into _a and to mark it, write the mark on the space. Have to adapt the machine such that it skips past these spaces when reading (extra states in all transitions). Additionally, should modify machine to use a new symbol where it would normally use the empty spaces.

One thing to note for both: consider how the copying could be implemented—using extra states or by extending the alphabet.

TM with doubly infinite tape: tape has no left endpoint. To prove: these recognize the class of Turing-recognizable languages.

Answer:

Suppose we have regular TM recognizing language. Then we create a doubly infinite one where we initially mark the square left of the input by \(\#\). All states get self-loop with \(\#,R\). We can now simulate the regular TM using a doubly-infinite one.

Note that by shifting input arbitrarily to the right (as needed), ordinary TM can emulate doubly-infinite TM. Put some marker on the left-most end of the tape and if we ever want to move further left, shift everything to the right first.

Alternative suggestions:

• Use multi-tape TM where tape 1 is starting point and everything to the right while tape 2 is everything to the left of start in reverse order
  • Have to make a copy of states with movement reversed on tape 2
  • Have to detect when to switch between the two
  • Considering how to implement multi-tape, this would look somewhat similar to above approach “in practice”
• Make clever mapping such that every odd-numbered \(n\) cell is \((n-1)/2\) on infinite tape while every even-numbered cell except the first one (could use a marker) is distance \((n-2)/2\) to the left of start.

TM with stay put instead of left: can go right or not move. Never goes to the left again. Show: not equivalent to normal TM, consider what can be recognized.

Answer:

Intuition: can probably recognize regular languages (have only states and no “memory” as it cannot move backward). It is trivial to prove that stay-put TMs can recognize at least the set of regular languages.

To show that they can only recognize regular, consider how to create an NFA from a stay-put TM (staying put is epsilon). Some care has to be taken if the TM stays while rewriting and changing states (note that doing so does not give it any useful “memory” and we can simulate this using extra NFA states).

Implementation details left to the reader. Main observation: as the TM has finite alphabet finite number of states, anything it can accomplish by standing still and writing to the same cell can be encoded in a finite number of states of an NFA (and of course, writing while moving to the right makes no difference when it cannot go back).

Consider problem of showing whether a DFA and a regular expression are equivalent. Formulate as language and show decidable.

Answer:

As a language:

To determine language, we need to test if the DFA is equivalent to the regex. Recall the following facts:

1. Can make DFA from regex
2. Regular languages closed under intersection and complement (therefore also set difference)
3. \(A=B \iff A \setminus B = B \setminus A = \emptyset\)
4. We can decide if a given DFA will accept any string

This one is easy if you know theorem 4.4. Very easy if you know theorem 4.5 (then we only need step 1).

Show: language of CFGs which generate the empty string is decidable.

Answer: In the input, we will have the set of variables. We say that a variable is nullable if it can be rewritten to epsilon or a sequence of nullable variables. We can repeatedly go through all transitions, marking more variables nullable. If the starting variable becomes nullable, epsilon can be generated. If not and no changes are found in an iteration (finite number of variables, rules so this terminates), epsilon cannot be generated.

Short version: convert to Chomsky normal form (this does the whole nullability thing as part of the conversion) and check whether or not the starting variable can be rewritten to epsilon.

Show: \(\overline{E_{\text{TM}}}\) is Turing-recognizable.

Answer: Once again, consider all strings over \(\Sigma^*\): \(s_1, s_2, \dots\). We make a TM that, given \(\langle M \rangle\) as input will:

• for \(i = 1, 2, \dots\)
  • simulate \(M\) on \(s_1, s_2, \dots, s_i\) for \(i\) steps
  • if any of those simulations end in accept, then accept (the corresponding \(s_k\) proves that the language of \(M\) is not empty)

Show: this set is uncountable.

Answer: This exact example is illustrated nicely on Wikipedia. Given any enumeration \(s_1, s_2, \dots\) of these infinite strings, create a string which in position \(i\) differs for \(s_i\) at this position (swap 0 and 1 in this case). By construction, this string is not in the enumeration.

Show: this set is countable.

Answer: Recall the Cantor pairing function seen in the discrete math course to show that the set of rational numbers is countable. This sort of argument, we can just apply twice.

Or even better, recall (also from discrete math—we proved this via induction in an exercise) that the Cartesian product of finitely many countable sets is countable.

We say that a variable \(A\) in CFG \(G\) is usable if it appears in derivation of some string \(w \in L(G)\). Problem: given \(G\) and \(A\), check if \(A\) is usable. Formulate as language, show it is decidable.

Answer: Language formulation omitted here. To decide:

1. Variable must be reachable
   1. \(S\) is reachable
   2. If \(A\) is reachable and \(A \to s_1 B s_2\), then \(B\) is reachable
2. Variable must derive terminals (let’s say it must be generating)
   1. All variables deriving terminals are generating
   2. If \(A \to BCD\) and \(BCD\) are all generating, \(A\) is generating

Both the sets (reachable and generating variables) can be computed by iterating over grammar a finite number of times. \(A\) must be in intersection.

Note: this is not quite enough. How can we avoid a false positive in the event that \(A\) is only reachable in a derivation where non-terminating variables are also produced?

Show: it is decidable.

Answer:

In case we are to check if \(L(G)\) is infinite: there will, for long enough strings, be some reuse of varialbes (think of pumping lemma proof). This comes from cyclic behavior in expansions. Check if any variable can derive itself (potentially via some intermediaries)—this can be done using a finite number of cycle-detection schemes.

In case \(k\) is finite, we can first make sure the language is actually finite using the approach just described. Now, to make sure that the number of strings of the finite language is exactly \(k\), we can exploit the fact that there will be a limit on the length of the strings we would need to check (refer to pumping lemma for rough upper bound). As such length is finite, we can enumerate and test all such strings (thm. 4.7 says that \(A_{\text{CFG}}\) is decidable). Can potentially lower the number of derivations to try, but this is not important.

From now on: in definitions, I probably omit stuff like “\(M\) is a DFA” because it’s usually implied (you should always write it in your assignments still).

Show: it is decidable (hint is to use some theorems about CFLs).

Answer: We only need the following three ingredients:

• We can come up with a CFG generating all palindromes
• We can also intersect a context-free language with a regular language to get a context-free language
• Finally, \(E_{\text{CFG}}\) is decidable

Show:

1. PREFIX-FREE(REX) is decidable (given regular expression, decide if its language is prefix free)
2. How the same approach does not work to decide PREFIX-FREE(CFG)

Answer: convert regex to DFA. For one accepted string to be a prefix of another, the corresponding run through the machine (must be deterministic for this argument) goes from start to some accept to some (maybe even the same) accept again. So do some graph traversal:

• Which accept states are reachable from start?
• For each of these, can any accept state be reached?

If yes for any in the second case, then the language is not prefix-free.

Second part, PDA attempt at proof does not really work as traversing the digraph representation does not really cover the language properly. Not all CFGs even have a deterministic PDAs.

Show that the following is decidable:

Answer: Again, this is just a matter of recalling useful facts and theorems:

• Intersecting a context free language with a regular language gives a context free language
• \(1^*\) is regular, so \(1^* \cap L(G)\) is context free
• We know from thm. 4.8 that \(E_{\text{CFG}}\) is decidable

Show: can decide whether a given DFA generates an infinite language.

Answer: Digraph cycle idea: to recognize infinitely many strings, there must be some cycle and from (or on) the cycle, it must be possible to reach an accept state.

Language intersection idea: machine having \(n\) states can only accept strings of length \(\leq n-1\) without having to resort to cycles (refer to proof of pumping lemma).

• We can create DFA of all \(w \in \Sigma^*\) where \(|w| \geq n\)
• We can intersect it with input DFA
• We can check if resulting language is empty
  • If no, original DFA generates strings long enough that language must be infinite
  • If yes, original DFA had finite language

Brute force version: check all strings of length \(n \leq k < 2n\) (same purpose as intersection).

Post Correspondence Problem, find match in:

Answer: I found

Or:

ab|ab|aba|b|b|a a|a a
ab ab|aba b|b|a|a|a|a

Does \(A \leq_m B\) for regular \(B\) imply that \(A\) is regular?

Answer: No! Prove false using contradiction. Favorite non-regular yet context-free language: \(A = \left\{ a^ib^i\ \mid\ i \geq 0 \right\}\). Choice of \(B\) depends on the computable function we wish to construct.

\(B = \left\{ a \right\}\) is finite and therefore regular. Since \(A_{\text{CFG}}\) is decidable, the following is a computable function:

We see that \(w \in A \iff f(w)\) by construction, so \(A \leq_m B\). But \(A\) is not regular.

Show: \(A_{\text{TM}}\) not mapping reducible to \(E_{\text{TM}}\) (no computable function reduces the former to the latter).

Answer: Suppose it was mapping reducible via some computable function \(f\). Can use on complements (biimplication in definition);

• We have shown that \(\overline{E_{\text{TM}}}\) is recognizable
• Corollary 4.23 states that \(\overline{A_{\text{TM}}}\) is not
• We get a contradiction via thm. 5.28 (\(A \leq_m B\) and \(B\) recognizable means \(A\) recognizable)

Prove: \(\leq_{m}\) is transitive. That is,

Answer: Just write it out. We know there are two functions:

And we need to find \(h\) (actually, TM computing \(h\)) such that:

We construct TM for \(h\) as follows: given some input \(w\):

• run \(M_f\), leaving \(w' = f(w)\) on tape
• run \(M_g\), leaving \(w'' = g(f(w))\) on tape

So \(h = g \circ f\) and by definition of \(f\) and \(g\), we know that \(w \in A \iff w'' \in C\).

Show: undecidable. Hint: use Post Correspondence Problem (book shows reduction strategy—not depicted here).

Answer: we just want to argue that the reduction presented in the book is valid. That is, the PCP instance generated has a match if and only if the grammar is ambiguous.

Suppose the PCP instance has a match. Consider the ordered multiset giving same string above and below. Can use this to get derivation sequences in grammar. Same strings generated via \(T\) and \(B\) (\(a_i\) only relevant for other direction of proof).

Suppose CFG is ambiguous. Note that the \(a_i\) are new, unique and always at the end of strings, so any string derived from \(T\) is “unique” in this part of the grammar. To generate the same string via \(B\) (only way to get ambiguity), we have to get some \(b\) strings to match the \(t\) strings—but the \(a\) parts ensure that the \(t\) and \(b\) parts used come from matching pairs in the PCP instance.

Show: \(A\) is Turing-recognizable iff \(A \leq_m A_{\text{TM}}\).

Answer: Important: just have to show recognizable and not decidable.

Suppose \(A\) is Turing-recognizable. Take machine \(M_A\) recognizing \(A\). The following computible function is trivial: \(f(w) = \langle M_A, w \rangle\).

• If \(w \in A\), then \(f(w) \in A_{\text{TM}}\)
• If \(f(w) \in A_{\text{TM}}\), then \(w \in A\)

Thus \(A \leq_m A_{\text{TM}}\).

Suppose now that \(A \leq_m A_{\text{TM}}\) (want to show that \(A\) is recognizable). Take the function \(f\) computed by \(M_f\) where we know:

We know taht \(A_{\text{TM}}\) is recognizable, so can compute \(f(w)\) recognize if \(f(w) \in A_{\text{TM}}\) and therefore \(w \in A\).

Show: \(A\) decidable iff \(A \leq_m 0^* 1^*\).

Answer:

Suppose \(A\) decidable, show reducible. Because \(A\) is decidable, the following function is computable:

Second case just needs to be not in \(0^*1^*\). Observe that by construction, \(f\) is a reduction function.

Suppose reducible, show decidable. Consider reduction function \(f\) which is computable. To decide, given any \(w\), whether \(w \in A\), just:

• Compute \(f(w)\)
• Check if \(f(w) \in 0^*1^*\) (trivial)
  • If yes, accept
  • If no, reject

Prove Rice’s theorem. \(P\): nontrivial property of language meaning it contains some but not all TM descriptions. And:

(membership of \(P\) depends only on language of TM)

Answer: Proof is tricky, here is annotated version: assume for contradiction decidable for some \(P\) and use this to decide \(A_{\text{TM}}\). Assume \(M_{\emptyset}\) (where \(L(M_{\emptyset}) = \emptyset\)) is not in \(P\). We can take some \(M_P \in P\) because \(P\) is nontrivial. Now, given some \(\langle M, w \rangle\):

• Create a TM \(M'\) which does the following when given \(x\) as input:
  • Simulate \(M\) on \(w\), reject if it rejects
    • Note that this may loop
    • If always looping or rejecting, \(L(M') = \emptyset\)
  • Simulate \(M_P\) on \(x\), accept if it accepts
• Use decider for \(P\) to decide if \(\langle M' \rangle \in P\), accept if it is (reject otherwise)

The point of this construction is that \(\langle M'\rangle \in P\) if and only if \(\langle M, w\rangle \in A_{\text{TM}}\).

Suppose the constructed \(\langle M' \rangle \in P\). This means that \(M'\) gets past the part where it simulates \(M\) on \(w\) (if it didn’t, the language would be empty as it would reject / loop on any \(x\)) to simulate \(M_P\) on \(x\).

Suppose now that \(\langle M, w \rangle \in A_{\text{TM}}\). This means that \(M'\) gets to simulate \(M_P\) on \(x\) which means that \(\langle M' \rangle \in P\) by construction (could also do contraposition here).

Use Rice’s theorem to prove some languages undecidable.

Show that the following problem is undecidable (formulate as language first): does a given single-tape TM ever write the blank symbol over a nonblank symbol for any given input string?

Answer: as a language

Suppose for contradiction this is decided by TM \(M_A\). Then we can decide \(A_{\text{TM}}\): given \(\langle M, w \rangle\),

• Create a TM \(M'\)
  • Simulate slightly modified \(M\) on \(w\)
    • We don’t want this simulation to write blank over non-blank; can avoid this by carefully replacing blank character writes during simulation with some new symbol
  • If it accepts, write blank over some non-blank symbol (can write non-blank first to have something to overwrite in case there is nothing)
• Simulate \(M_A\) on \(M'\), accept if it accepts (reject otherwise)

By construction, \(M'\) will write the blank symbol on a non-blank cell if and only if \(M\) accepts \(w\).

In a TM: a useless state is a state that is never encountered on any input string. Formulate as language the problem of determining whether a TM has any useless states and show that this is undecidable.

Answer: As a language, this problem is

where one might add that a useless state \(q\) means

We will be reducing from \(A_{\text{TM}}\). Plan: given \(\langle M, w \rangle\), make a TM where accept state is useless iff \(M\) does not accept on \(w\). This \(M'\) should just reject on any \(w' \neq w\). Then, when run on \(w\), we want to make sure that, when rejecting, it uses all states except accept. Otherwise, one of the other states could be useless—and we only want accept to potentially be useless.

We can get it to visit all states except accept by introducing a new character on the tape and adding transitions on this character that form a tour of the states. In the machine I describe below, this tour should end in the reject state.

So, suppose \(M_U\) decides USELESS. Create new \(M'\) which given \(\langle M, w \rangle\) will:

• Create new \(M''\) based on \(M\) which takes input \(x\):
  • All transitions to reject state are replaced by tour to every non-accept state before rejecting
  • If \(x \neq w\), then reject
  • Otherwise run as normal on \(x\)
• Now, run \(M_U\) on \(M''\)
  • If it accepts, then accept state was useless and so reject
  • If it rejects, then all states were useful (including accept), so accept

Think about: why do we not need to do tour before accepting? Could we structure the machine (including when to do a tour) differently?

Describe how to formally encode an arbitrary digraph as binary string as an adjacency matrix and as an adjacency list.

Answer:

• Adjacency matrix
  • Need \(n \times n\) matrix
  • Can give \(n\) in unary via 1s (end with 0) to avoid having to worry about word length
  • Knowing \(n\), we can just list the \(n^2\) entries with 0 or 1
• Adjacency list
  • Can again give \(n\) (necessary?)
  • For each node:
    • Give number of outgoing arcs (could be in unary)
    • Then give ID for each target (could be in in unary; then, each ID would be long number separated by 0)

Show: if an algorithm makes at most constant calls to poly-time subroutines and does poly-time additional work, then the algorithm is poly-time. Also: show polynomial number of calls to polynomial-time subroutines may give exponential-time algorithm.

Answer: First, simply observe that:

Now, suppose we have some algorithm polynomial in its input:

poly(n):
  for i=1 to n
    do something uninteresting

Now, we make an algorithm calling it polynomially many times:

notsopoly(n):
  m = 1
  for i=1 to n
    m = m*2
    poly(m)

Observe that the final call will have the value \(m=2^n\), so the poly-time algorithm will do work that is exponential in the value of \(n\) as seen by notsopoly.

Show: if HAM-CYCLE is in P, then we can list vertices of such a cycle in order in poly-time. Keep in mind: HAM-CYCLE only tells us whether a hamiltonian cycle exists in the graph. Problem is to extract (and sort) it.

Answer: We assume that there is a Hamiltonian cycle (at least one) in the graph before starting (otherwise there is nothing to do). Idea: throw out edges until only such a cycle remains. Given \(G=(V,E)\):

• for each \(e \in E\)
  • \(G' = (V, E \setminus \{e\})\)
  • call HAM-CYCLE on \(G'\)
  • if there is still a cycle in \(G'\):
    • \(G \gets G'\)

This is polynomially many calls to HAM-CYCLE and afterwards, \(G\) will only contains edges on such a Hamiltonian cycle. Using any graph traversal we choose, starting at any vertex, we can now list the vertices of \(G\) in the order the cycle visits them.

Suppose: have language \(L\) and algorithm accepting string \(x \in L\) in poly-time, but rejecting \(x \notin L\) in super-polynomial time. Show: can then decide \(L\) in polytime.

Answer: if we know a (possibly rough) polynomial \(n^k\) bound for the running time in case \(x \in L\), then we can simply run the given algorithm for that amount of time (number of steps). If it has not accepted by then, we can safely reject.

Also, note that on pages 1059-1060 in Cormen, the proof of theorem 34.2 is essentially stating this exact argument.

Prove: NP closed under regular operations. In all situations, we have two languages with each their own verification machines.

Answer:

Union: Here, we have two “obvious” options. One is (like with union for Turing-decidable languages) to simply take as certificate a certificate from either of the two languages and run both verification machines on it, accepting if either one does so. The other is to let the certificate be a flag indicating which of the two languages a given string belongs to and based on this, run the corresponding verifier.

Intersection: Try to verify using verifier for both languages. If both accept, accept. Since the two verifiers may have different certificates, we should define certificates for the intersection such that the certificates needed by both machines are included—simplest way would be to concatenate them with an indication of which part belongs to which original certificate.

Concatenation: Combine two certificates with some marker to indicate where to split input string. Then run each machine on each part and accept if both do.

We are supposed to skip Kleene star.

\(\phi\) is a boolean formula over variables \(x_1, x_2, \dots, x_k\). Has \(\neg\), \(\wedge\), \(\vee\) and \(()\). The language TAUTOLOGY is the language of all such formulae which are tautologies. Show that TAUTOLOGY is in co-NP (that is, the complement of TAUTOLOGY is in NP)..

Answer: Suppose we have \(\phi\) which is not a tautology. This means that for some assignment of truth values to variables in \(\phi\), \(\phi\) is false. Given this assignment and \(\phi\), it is trivial to verify that \(\phi\) can, indeed, be falsified (just insert the values and evaluate).

Show: Only \(\emptyset\) and \(\{0,1\}^*\) are not complete in P wrt. poly-time reductions.

Recall: \(L_1 \leq_p L_2\) iff there is poly-time computable \(f: \{0,1\}^* \to \{0,1\}^*\) s.t.:

Answer: Suppose we have a \(L_2\) which is neither empty nor every possible string. Then there is some string \(a \in L_2\) and string \(b \notin L_2\). Take any \(L_1\) from P; the following function is trivially computable in poly-time (as \(L_1\) is in P):

This approach obviously does not work for \(\emptyset\) and \(\{0,1\}^*\) because it is not possible to use them to “distinguish”.

Algorithm for finding factors of a number: given input \(n \in \mathbb{N}\), do

1. for \(i=2\) to \(n-1\)
   1. if \(i\) divides \(n\), output \(i\)
2. if nothing output, output \(-1\)

Claim that checking whether a number divides another in \(O(log^3 n)\) time:

• multiplication can be done in \(O(\log^2 n)\) on binary representation of \(n\)
• could use binary search \(O(\log n)\) steps to find \(k\) s.t. \(ik=n\)

So total running time of algorithm to find factors is \(O(n \log^3 n)\). Why does this not break RSA?

Answer: consider what the “input size” for our problem is. The time arguments made rely on the value or magnitude of \(n\). However, input size is not the same as the value of the single number \(n\).

It would probably be expressed as a binary number where the input size would be number of bits; the magnitude of the number would then be exponential in the “size of the input”.

Consider a formula with exactly three literals per clause. We want to add a constant number of three-literal clauses that will make any such formula false.

Answer: just choose (or add) three arbitrary literals and add the eight clauss consisting of every different regular / negated version of them:

Show: any language in NP could be decided by algorithm running in \(2^{O\left(n^k\right)}\) where \(k\) is some constant.

Answer: Idea by certificates: by definition of NP, any yes-instance has poly-length certificate which can be checked in poly-time. We can enumerate certificates and try them.

Let’s be more formal. On page 1064 of the textbook, the definition is that \(L\) is in NP iff there is a polynomial-time algorithm \(A\) and constant \(c\) such that:

There will be \(2^{O(n^c)}\) certificates to try and \(A\) runs in polynomial time, say bounded by \(O(n^{a})\).

• \(2^{O(n^c)}\) certificates
• Each of length \(O(n^c)\) thus taking time \(O((n^c)^a) = O(n^{ca})\) to run \(A\) on one
• For a total of \(2^{O(n^c)} \cdot O(n^{ca})\) time to try them all

Setting a sufficiently large \(k\), the total time is definitely bounded asymptotically by \(2^{O(n^k)}\). A quick choice could be \(k=2ca\).

Prove: if NP \(\neq\) co-NP, then P \(\neq\) NP.

Answer: We will use our favorite proof method: contraposition. Suppose P equals NP. This would mean that, for any problem in NP, we can find a solution in poly-time (decider). Then consider the complement; we can just check if any given instance is in the original language and answer in the negative of the result (P is closed under complement due to argument like an exercise from last time). So then P=NP=co-NP.

Prove: \(L\) is complete for NP wrt. poly-time reductions iff \(\overline{L}\) is complete for co-NP.

Answer: Suppose \(L\) is complete in NP. Recall that this means that for any \(L'\) in NP, there is a function \(f\) where \(x \in L' \iff f(x) \in L\). We can just take complements;

Observe that this is a polynomial reduction from \(\overline{L'}\) which is in co-NP to \(\overline{L}\). This goes both ways, so \(\overline{L}\) is complete in co-NP.

Going right-to-left is just a matter of playing the equivalences / biimplications backwards.

Show: determining if boolean formula is tautology is complete in co-NP. Hint: use exercise 34.3-7 which asks to prove that \(L\) is complete in NP iff \(\overline{L}\) is complete in co-NP.

Note: we have previously shown that TAUTOLOGY is in co-NP (34.2-8).

Answer: Let’s call the complement of TAUTOLOGY FALSIFIABLE. Can make poly-time reduction from SAT to FALSIFIABLE (claim), so FALSIFIABLE is complete in NP. Via 34.3-7, we conclude then that TAUTOLOGY is complete in co-NP.

To expound on the claim that SAT can be reduced to FALSIFIABLE: recall that an instance of SAT is a formula \(\phi\) and the goal is to determine if it can be satisfied. Note that any assignment that makes \(\phi\) true will make \(\neg \phi\) false—so our reduction is simply negating the formula, knowing that \(\neg \phi\) will be in FALSIFIABLE if and only if (since it will be due to the same assignment) \(\phi\) is in SAT.

Show: determining satisfiability of formula in DNF is poly-time solvable.

Answer: Since the formula is in DNF, we only need to satisfy one clause. For each clause, try to assign values to satisfy it—there is only one way to do so, if any. If a clause proves to be a contradiction, just move along to the next one. If any satisfiable clause is found, we have satisfying (partial) assignment. Else, no solution exists.

Suppose: we have poly-time algorithm for SAT. How to find concrete assignment in poly-time?

Answer: Assume that the formula is initially satisfied (otherwise this is boring).

• start with empty assignment; \(f(x) := ?\) for all variables \(x\)
• for each variable \(x\):
  • assign to true; setting \(f(x) := \text{true}\)
    • meaning we modify the formula such that each occurrence of \(x\) is replaced by “true”
    • if we don’t want to have “true” in the formula, the modification could be done equivalently by removing occurrences of \(x\) along with any parts satisfied by \(x\)
  • if the modified formula is still satisfiable, this was a correct (or irrelevant) assignment
  • if however the modified formula is now unsatisfiable, set instead \(f(x) := \text{true}\)
    • note that the formula modified according to this must be satisfiable again

When this terminates (in case we remove satisfied parts, it may terminate early when the remaining formula is empty), \(f\) is a (maybe partial) assignment satisfying the formula.

Consider 2-CNF-SAT. Show that it is in P. Make efficient algorithm. Use \(x \vee y \equiv \neg x \implies y\) and reduce the problem to efficiently solvable digraph problem.

Answer:

Digraph version: make \(D=(V,A)\) where \(V\) consists of all variables in regular and negated form. \(A\) is then implications. Observe that \(D\) has size polynomial in the size of the formula.

The \((x \vee y) \equiv (\neg x \implies y) \equiv (\neg y \implies x)\) implications (now represented as arcs) each means that if \(\neg x\) is true, then \(y\) has to be true, too. As only one of \(x\) and \(\neg x\) can be true, cycles would be a problem. If there is a cycle containing any variable and its negation, then there cannot be a satisfying assignment.

Below, the digraph representing \(\neg x \vee y\), \(\neg y \vee z\), \(\neg z \vee \neg y\), and \(y \vee x\) is shown as an example. Arcs colored red and blue for “symmetric” arcs: for \(\neg x \vee y\), the arc \(x \to y\) is blue and \(\neg y \to \neg x\) is red.

Note that there is clearly cycles between both regular and negated vertices for the same variables; for instance \(x \to y \to \neg z \to \neg y \to x\). To verify for yourself that this formula cannot indeed be satisfied, observe the following truth table:

Now, to find an algorithm to check this. Naive approach: for each variable, see if there is path to its negation (could use DFS) and back again. This would be \(\Theta(n(n+m))\). Could use Floyd-Warshall to achieve this in \(\Theta(n^3)\) and then if for any \(x\), distance from \(x\) to \(\neg x\) is finite and \(\neg x\) to \(x\) is, too.

If we know how to find SCCs: In a strongly connected component, there can be no solution iff any \(x\) and its corresponding \(\neg x\) are in the same SCC (by above argument, all literals / vertices in the same SCC have the same value). After building graph, find all SCCs in \(O(m+n)\) and check if any variables have both nodes in same SCC. With some consideration, we could do each such check in constant time and thus stay in \(O(m+n)\).

Recall definition of isomorphic (as it pertains to graphs). \(G_1\) and \(G_2\) are isomorphic if there exists a bijection \(f: V_1 \to V_2\) on the vertex sets such that for all \(v_i, v_j \in V_1\), \((v_i, v_j) \in E_1 \iff (f(v_i), f(v_j)) \in E_2\).

Show: subgraph-isomorphism problem NP-complete. The problem is, given \(G_1\) and \(G_2\) to determine if \(G_1\) is isomorphic to a(n induced) subgraph of \(G_2\).

Answer: Just have to think of a suitable well-known NP-complete graph problem to use. Let’s make a reduction from CLIQUE.

• Clique instance: \(G=(V,E), L\) and the question is whether there is a clique of size \(L\) in \(G\)
• We create a subgraph-isomorphism instance \(C_L, G\)
  • \(G\) is the original graph from CLIQUE (we clearly want to find something in this graph)
  • \(C_L\) is a clique of size \(L\) that we simply construct

Finding \(C_L\) in \(G\) is exactly finding a clique of size \(L\), so correctness of the reduction is pretty trivial.

Just to make sure that the reduction is polynomial: we only need to consider \(|C_L| \leq |G|\). That is, if \(L > |V|\) or if \(\frac{L(L-1)}{2} > |E|\), we can just answer no instead of creating \(C_L\) at all.

Assume we have a poly-time algorithm solving the subgraph-isomorphism (decision) problem. Use this to find an isomorphism.

Answer: First, we can remove unnecessary nodes from second graph (remove one at a time, add if it removes all mappings). Secondly, we need to determine a bijection between the two vertex sets remaining.

Silly (yet polynomial) strategy: individualize vertices by adding a unique subgraph outside (maybe just a clique of size \(n+1\)) and connecting to only one node on both sides.

Faster (but to me less obviously correct): remove vertex in second graph one at a time. For each one, find the corresponding vertex in first graph by removing one at a time here.

Show: 0-1-integer programming problem NP-complete via reduction from 3-CNF-SAT.

Answer:

Let \(A\) have dimensions \(m \times n\) where \(m\) is number of clauses and \(n\) is number of variables. The 0/1-vector \(x\) will have \(n\) entries, each representing a variable (0 for false, 1 for true).

Each row in \(A\) models a clause; it has only 3 non-zero entries (one for each literal appearing in the clause). These non-zero entries are 1 for negated variables and -1 for regular ones. The corresponding row in \(b\) will have value equal to number of negated variables minus one.

Example: \((\neg x_1 \vee x_2 \vee x_3)\) will in \(A\) appear as \(1\ -1\ -1\). Looking in the truth table below, the row with 100 (making this clase false) is bad and causes has sum 1 where it shoudl be \(\leq 0\). All others fine and have sum \(\leq 0\).

Try reduction from vertex cover to 0-1-integer programming. Instance of vertex cover is graph \(G=(V,E)\) and number \(k\), asking whether a cover \(C \subset V\) exists where \(|C| \leq k\). Note: the cover covers all edges, that is \(\forall \{u,v\} \in E: u \in C \vee v \in C\).

Answer: Here, \(A\) can have dimensions \(m \times n\) such that each row represents an edge (has two non-zero entries indicating endpoints). If endpoints are -1 and \(x\) has entries 1 for each selected node, then each entry of \(b\) is just -1.

Problem: resolve the problem that this only gives a vertex cover. What about guaranteeing that it has size something? Idea: add an extra row which counts the number of selected vertices. Row should have all ones. Corresponding entry in \(b\) should be \(k\).

Show: if target value of subset-sum problem is given in unary, the problem can be solved in poly-time. Look at pages 1128-1129 for a hint.

Recall: a subset-sum problem instance is a pair \((S,t)\) where \(S\) is a set of positive integers \(\{x_1, \dots, x_n\}\) and \(t\) is a positive integer. Question is whether there exists a subset of \(S\) summing to exactly \(t\).

Answer: the point in this exercise is that the target value expressed in unary will have magnitude polynomial in input size (well, equal to, pretty much). The book (following the hint) gives an “exponential-time” exact algorithm. It is exponential because the lists \(L_i\) can reach length up to \(2^i\). However, as we are dealing with positive integers, we don’t really care about lists longer than \(t\) as they will include elements greater than \(t\) (and so would be thrown away anyway).

So we could just use the merge-list-based exact sum algorithm from the book because this is polynomial in the value of the target \(t\). In fact, the book mentions this already; the algorithm is polynomial-time in case \(t\) is polynomial in \(|S|\) or all numbers in \(S\) are polynomially bounded by \(|S|\).

Also: Any pseudopolynomial solution will be polynomial in this setting. Example: dynamic programming solution which takes time \(O(sn)\) where \(s\) is sum to hit.

numbers = [1,5,6,13,14]
target = 20

# Q[i][j]: can sum of subset of S[:i] be j?
Q = [[False for j in range(target+1)]
     for i in range(len(numbers))]

for i in range(len(numbers)):
    val = numbers[i]
    Q[i][0] = True # can always hit 0
    for j in range(1, target+1):
        Q[i][j] = \
            (val == j) or \
            Q[i-1][j] or \
            (j>=val and Q[i-1][j-val])

print(Q[-1][-1])

True

Show: set-partition problem is NP-complete.

Instance is \(S\) which is just a set of numbers. Question is whether \(S\) can be partitioned into two sets such that each of these two sets has the same sum.

We are allowed to redefine set partition to allow the same value to appear more than once.

Answer:

Trivial part: argue it is in NP. Omitted here.

Reduction from subset-sum. Consider subset-sum instance:

Let \(S = \sum_{i=1}^{n}a_i\). Create then an instance \(A' = A \cup \{S - 2t\}\) of set partition. We now prove this is a valid reduction (given: it is polynomial).

Suppose there exists a subset \(B \subseteq A\) s.t. \(\sum B = t\) (solution to subset sum). Then,

so there exists a satisfying partition.

Suppose there is a satisfying partition. Each must have sum \(S-t\) by construction. One of the parts, \(B'\) will contain the element \(S-2t\). Removing this element, we see that \(\sum(B' \setminus \{S-2t\}) = t\), so we have the subset sum solution right there.

Reduction found in old notes: choose some \(w > \max\{S,t\}\) and use partition instance \(A \cup \{w-t, w-S+t\}\) (generalization).

Show: hamiltonian-path problem is NP-complete. Recall: hamiltonian path is just a simple path visiting each vertex exactly once (like HAM-CYCLE, but path instead of cycle).

Answer:

Trivial: it is in NP. Reduction from HAM-CYCLE instance \(G=(V,E)\):

• for each \(e \in E\):
  • create new graph without this edge, \(G' = (V, E\setminus \{e\})\)
  • for the two endpoints, add new nodes with only connections to these endpoints such that any path ham-path will start/end here
    • \(e = \{u,v\}\)
    • add nodes \(s_u\) and \(s_v\) to \(G'\)
    • add edges \(\{s_u,u\}\) and \(\{s_v,v\}\) to \(G'\)
  • if there is a HAM-PATH \(p\) in \(G'\), there was a HAM-CYCLE \(p \setminus \{\{s_u,u\},\{s_v,v\}\} \cup \{e\}\) using the removed edge in the original graph (and vice versa)

We consider a bunch of variations on problems involving a bag of money to be divided between Bonnie and Clyde. For each problem, either show that it is NP-complete or give a poly-time algorithm.

Working with graph coloring. An instance is \(G\) and it is minimization problem (minimum number of colors). Will end up showing that the decision problem 3-COLOR is NP-complete.

Show: can find median of five elements using six comparisons in worst case.

Answer:

Start by comparing two pairs of elements. Suppose a<b and c<d. Then, compare the two losers; suppose a<c. We can discard a now.

We have now b (bigger than one element), c (smaller than one, bigger than one), d (bigger than one) and e (uncompared). We compare b with e and have two cases:

• b<e means we have two “chains” a<c<d and a<b<e
  • compare and wlog assume c<b (symmetric)
    • now a<c<d and a<c<b<e means only d or b can be median; take the smaller one
• b>e means we have (a,e)<b and a<c<d
  • compare e with c, giving two cases
    • e<c means (a,e)<b and (a,e)<c<d so only b, c remain as candidates; take smaller one
    • e>c means a<c<d and a<c<e<b, leaving d,e as candidates; take smaller one

Have sorted lists of length \(n\) and \(m\), wish to merge. Prove (tight) lower bound of \(n+m-1\).

Answer:

Consider final list of length \(n+m\). If only \(n+m-2\) comparisons were used, there must be a pair of consecutive elements which were not compared. Suppose these came from two different lists (can create input so this happens); we can then run the algorithm again where they should be from same list and as the algorithm cannot distinguish, it will be wrong in one case.

Question is: does a given bit string contain two consecutive zeros? For sizes of 2 to 5, give either an adversary algorithm forcing any algorithm to query every bit or give an algorithm that is correct without querying all bits.

Answer:

• n=2 obvious adversary: say 0 first (have to check the other)
• n=3 almost obvious adversary
  • if 2 is queried, answer 0 (from here, obvious)
  • if 1 or 3 is queried, answer 1 and proceed with n=2 strategy
• n=4 has algorithm querying only 3 bits, starting with 2
  • if _1__, we can ignore index 1 and proceed with 3,4 (3 checks in total)
  • if _0__, query index 3
    • if _00_, done
    • if _01_, we can ignore 4 and need only check 1 (3 checks in total)
• n=5 has clever adversary; for any query, we give response
  • if 1 is queried, answer 0 0____
    • 01___ reduces to n=3
    • 0_1__ reduces to n=2 and 2 must be queried
    • 0__0_ can force all to be queried (answer 1)
    • 0___1
      • 01__1 reduces to n=2
      • 0_0_1 remaining must be queried (answer 1)
      • 0__01 ditto
  • if 2 is queried, answer 0 _0___
    • 10___
      • 101__ n=2 remaining
      • 10_0_ both remaining must be queried (answer 1)
      • 10__0 ditto
    • _01__ already covered (will always set 1 to 1)
    • _0_0_ ditto
  • if 3 is queried, answer 1 __1__
    • this reduces to two cases of n=2 where adversary is known

L1 and L2 are arrays. Each has \(n\) keys and is sorted. Find the \(k\)’th smallest element.

Naive way: use maximum finder three times; first two times discarding maximum. This would take \(n-1+n-2+n-3=3n-6\) comparisons.

Could also: maintain top three all the time. Worst case involves swapping each time. Would require \(0+1+2+3(n-3)=3n-6\) comparisons.

For the regular “Cave Tunnels” (CT) problem, an instance has the form \((G=(V,E), k)\) where \(G\) is the graph corresponding to the given map of tunnels: \(V\) is the set of rooms with \(|V|=n\) and \(\{u,v\} \in E\) if the rooms \(u\) and \(v\) are connected by a tunnel. The regular CT problem is to find the maximum number of tunnels which can be controlled by placing \(k\) blockers on nodes of the given graph.

Out of \(n\) people, \(2k\) have a virus and we need to find \(k\) of them.

For the information-theoretic lower bound, we ignore the people with the \(k\) highest identification numbers (these are assigned before the algorithm runs and not related to infection status).

We model all algorithms as binary decision trees in which each node corresponds to testing one person at a time (branching on whether or not the test is positive). We know from the slides that a \(t\)-ary tree with \(n\) leaves has height \(\left\lceil \log_t(n) \right\rceil\). The height of the decision tree will correspond to the number of tests performed in the worst case to reach a leaf corresponding to a result.

We thus need to count how many leaves the decision tree must have. The population to consider has size \(n-k\) and—depending on the input and which are ruled out by having the highest IDs—any subset of size \(k\) could be the correct answer. This leads to \({n-k \choose k}\) possible outputs or leaves. The straightforward lower bound achieved this way will therefore be: