# Problem Set 6
## Problem 1
### 1.1
(EXACT) CHROMATIC NUMBER problem involve two questions, one in NP and one in coNP.
1. Is the minimum chromatic number <= k (in NP)
2. Is the minimum chromatic number >= k (in coNP)
Chromatic number problem is NP-complete, Graph 3-Colorability is its special case.
We can use a Ptime oracle TM with an oracle for Chromatic number problem decision problem to answer the above 2 questions. Thus (EXACT) CHROMATIC NUMBER problem is in $P^{NP}$
### 1.2
#### $coNP \subseteq NP$
Since any $L \in coNP$ can reduce to coChromatic_number which is coNP-complete and can be further reduced to (EXACT) CHROMATIC NUMBER problem. Now (EXACT) CHROMATIC NUMBER problem is in NP, thus L is in NP.
#### $NP \subseteq coNP$
For any L ∈NP, its complement LC in coNP, thus LC can be reduced to coChromatic_number which is coNP-complete and can be further reduced to (EXACT) CHROMATIC NUMBER problem. Now (EXACT) CHROMATIC NUMBER problem is in NP, LC in NP, thus L in coNP.
### 1.3
#### $coNP \subseteq NP$
Since any $L \in coNP$ , its complement LC in NP, LC can be reduced to chromatic number problem which can be further reduced to (EXACT) CHROMATIC NUMBER problem. Now (EXACT) CHROMATIC NUMBER problem is in coNP, thus LC in coNP, thus L in NP.
#### $NP \subseteq coNP$
For any L ∈NP, it can be reduced to chromatic number problem which can be further reduced to (EXACT) CHROMATIC NUMBER problem. Now (EXACT) CHROMATIC NUMBER problem is in coNP, thus L in coNP.
## Problem 2
From the definition, we know that $\sum_2{P} = NP^{NP}$.
The problem: is formulae f1 not equivalent to formulae f2 is in NP. A NTM can guess an assignment and verify the value of the two formulaes with this assignment not equal.
We can solve this problem with an NP machine that guesses the conjunctive normal form with B or fewer clauses, then asks an oracle whether the conjunctive normal form is not equivalent to the original disjunctive normal form.
Thus, the problem is in $NP^{NP} = \sum_2{P} $
## Problem 3
Modify the proof that there is an oracle B such that $P^B ≠ NP^B$ as follows.
For any oracle $B \subseteq\{0,1\}*$, define the language
LB =$\{0^n|\exists x \in B\quad s.t\quad |x|=n\}$
For any B, $L_B \in NP^B$ . Given a string 0n , guess a binary string x of the same length, query if it is in B, and if it is then accept.
We’ll define a B such that LB differs from the language of any coNP-time machine with oracle B.
Enumerate **coNP-time** oracle machines M1, M2, … and assume that Mi runs in time at most $n^i$.
We’ll define B in stages, where stage i kills machine Mi
Before each stage i, we have specified for a finite set Si of strings whether they are in B or not.
Stage i. Take n large enough so that it exceeds the
length of all strings in Si and also $n^i \lt 2^n$.
Run Mi on input $0^n$ . If it queries a string in Si answer accordingly; if it queries another string answer No
At the end, if Mi accepts $0^n$, then specify that all (remaining) strings of length n are not in B
If Mi rejects $0^n$, then pick a string z of length n that Mi has not queried and add it to B ; **such a string z exists because machine Mi is in coNP, there is a rejection computation path with polynomial number of queries $n^i \lt 2^n$**.
Mi does the wrong thing on input 0n it does not accept LB
## Problem 4
### 4.1
A NTM can guess a string and then simulate each of the DFA to verify whether the string is accepted by all DFAs. Clearly, it uses polynomial space, thus the DFA Intersection problem is in NPSPACE. From the fact that NPSPACE = PSPACE, thus the DFA Intersection problem is in PSPACE.
### 4.2
Following the hint, I prove this with a reduction from the LBA problem.
Use for the common alphabet of the DFA the set of all tuples (q,a,i) consisting of a state q of the LBA, a tape symbol a and an index i=1,…,n of a tape cell. Given an input x to the LBA, for each tape cell，construct the DFA as follows:
The states for DFAs when LBA accept are accepting states. Suppose LBA has a transition (x, u, i) -> (y, v , j). Then For DFAi, have transition (x, u, i) -> (v, j) and DFAj have transition (u, i) -> (y, v, j). For other DFAs, have transition (u, i) -> (v, j).
Now the input is accepted by all the DFAs iff accepted by LBA. Thus, there is a reduction from the LBA problem to DFA Intersection problem . Thus, DFA Intersection problem is PSPACE-complete.
## Problem 5
### 5.1
### 2SAT for monotone formulas in #P
It is easy to see that we can use a NTM to compute all branches and count the number of satisfying assignments in polynomial time. Thus, #2SAT for monotone formulas in #P.
### 2SAT for monotone formulas is #P hard
Following the hint, I prove this by showing there is a parsimonious reduction from #P complete problem #Matchings problem to #2SAT for monotone formulas.
Use a Boolean variable for each edge denoting that the edge is not in the matching. For each pair of edges $e1$ and $e2$ that share one node, add the clause $e1 \vee e2$ .
We can show that matching and satisfying assignment has a one to one correspondence.
For a given matching, by definition for each pair of edges $e1$ and $e2$ that share one node, we can’t have both $e1$ and $e2$ in the matching, thus we can’t have both variables $e1$ adn $e2$ in #2SAT to be false, thus at least one of them is true, thus the clause $ e1 \vee e2$ is satisfied, and the corresponding assignment is a satisfying assignment.
For a given satisfying assignment, for eahc clause $e1 \vee e2$, $e1$ and $e2$ can’t be false at the same time, which means for each pair of edge $e1$ and $e2$ that share one node, $e1$ and $e2$ are not in the corresponding matching at the same time, thus it is a valid matching.
From above, #2SAT for monotone formulas is #P-complete.
### 5.2
### #Node Covers in #P
It is easy to see that we can use a NTM to compute all branches and count the number of node covers in polynomial time. Thus, #Node Covers in #P.
### #Node Covers is #P hard
I prove this by showing there is a parsimonious reduction from #2SAT for monotone formulas to #Node Covers.
For each variable $x$, create the node $v_x$, for each clause $x \vee y$ , create the edge $(v_x, v_y)$ . If $x$ is true in the assignment, then $v_x$ in the node cover.
We can show that each satisfying assignment corresponds to one node cover and each node cover corresponds to one satisfying assignment.
Given a satisfying assignment, for each clause $x \vee y$ , either $x$ or $y$ is true, thus either $v_x$ or $v_y$ in the node cover, thus the edge $(v_x, v_y)$ is covered. Thus, the corresponding node cover is a valid node cover.
Given a node cover, for each edge $(v_x, v_y)$, either $v_x$ or $v_y$ in the cover, thus either $x$ or $y$ is true, thus $x \vee y$ is true, thus the corresponding assignment is a satisfying assignment.
From above, #Node Covers is #P-complete.