# Week 12 Quiz

1. Given two decision problems $A$ and $B$, and $A \leq_P B$. If $A \in \mathsf{P}$, then $B \in \mathsf{P}$.
2. Given two decision problems $A$ and $B$, and $A \leq_P B$. If $A \in \mathsf{NP}$, then $B \in \mathsf{NP}$.
3. Given two decision problems $A$ and $B$, and $A \leq_P B$. If $B \in \mathsf{P}$, then $A \in \mathsf{NP}$.
4. Given two decision problems $A$ and $B$, and $A \leq_P B$. If $A \in \mathsf{NP}$-complete, then $B \in \mathsf{NP}$-complete.
5. ***3-SAT*** problem is **NP-complete**. Select ***ALL*** that we need to prove that a problem $A$ is **NP-complete**
- $A \leq_P$ ***3-SAT***
- ***3-SAT*** $\leq_P A$
- $A$ in $\mathsf{NP}$
- $A$ in $\mathsf{P}$
6. Let $A$ be a problem in $\mathsf{NP}$-hard. If we want to prove that a problem $B$ in $\mathsf{NP}$-hard, it is sufficient to show that $A \leq_P B$
7. Suppose in a parallel universe, we have proven $\mathsf{P} = \mathsf{NP}$. Select all statement(s) that is/are true
- All $\mathsf{NP}$-hard problems are solvable in polynomial time
- All $\mathsf{NP}$ problems are solvable in polynomial time
- All $\mathsf{NP}$-complete problems are solvable in polynomial time
- Some $\mathsf{NP}$-hard problems are solvable in polynomial time
8. Which of the following statement(s) *could* be true?
- ***3-SAT*** is solvable in polynomial time
- ***Maximum-Independent-Set*** problem cannot be solved in polynomial tme.
- Some NP-complete problems are solvable in polynomial time, while some cannot

## Solution

1. False, because it's possible that $B \in \mathsf{NP}$-hard (which means that $B \not\in \mathsf{P}$)
2. False, because it's possible that $B \in \mathsf{NP}$-hard, but $B \not\in \mathsf{NP}$
3. True, because $A \in P \subseteq NP$
4. False. It should be $B \in \mathsf{NP}$-hard.
5. We only need to prove two things:
- ***3-SAT*** $\leq_P A$
- Do the reduction in the right way! This proves that $A$ in $\mathsf{NP}$-hard! That's why we need to prove the one below
- $A$ in $\mathsf{NP}$
6. True, because showing $A \leq_P B$ shows $B$ is at least as hard as $A$. Therefore, $B$ is also $\mathsf{NP}$-hard

Side note: My intention of this question is to demonstrate that, let's say we cannot prove $A \leq_P B$, it's still possible that $B \in \mathsf{NP}$-hard. This is when $A$ is a harder problem than $B$. Not able to show $A \leq_P B$ does not imply that $B \not\in \mathsf{NP}$-hard.
7.
- All $\mathsf{NP}$-hard problems are solvable in polynomial time
- False, $\mathsf{NP}$-hard contains $\mathsf{NP}$-complete problems. $NP$-complete problems are solvable in polynomial time in this parallel universe.
- All $\mathsf{NP}$ problems are solvable in polynomial time
- True, because $\mathsf{P} = \mathsf{NP}$, then problems in $\mathsf{NP}$ is also in $\mathsf{P}$, which means that it's solvable in polynomial time
- All $\mathsf{NP}$-complete problems are solvable in polynomial time
- True, because $\mathsf{NP}$-complete problems are in $\mathsf{NP}$. Similar explanation in second point
- Some $\mathsf{NP}$-hard problems are solvable in polynomial time
- True, see explanation on first point.
8.
- ***3-SAT*** is solvable in polynomial time
- True if $\mathsf{P} = \mathsf{NP}$
- ***Maximum-Independent-Set*** problem cannot be solved in polynomial tme.
- True if $\mathsf{P} \neq \mathsf{NP}$
- Some NP-complete problems are solvable in polynomial time, while some cannot
- False. It's either ***all*** solvable in polynomial time, or ***all*** not solvable in polynomial time. Intuition: they have the same difficulty, i.e. hardest problems in $\mathsf{NP}$.

Let's say if a problem in $\mathsf{NP}$-complete is solvable in polynomial time. Then this implies that $\mathsf{P} = \mathsf{NP}$. All problems in $\mathsf{NP}$-complete is also solvable in polynomial time.

Let's say if a problem in $\mathsf{NP}$-complete is proven to be not solvable in polynomial time. Then this implies that $\mathsf{P} \neq \mathsf{NP}$. Therefore, all problems in $\mathsf{NP}$-complete are not solvable in polynomial time, because otherwise, $\mathsf{P} = \mathsf{NP}$, a contradiction.

## Tutor's Note

You can use the line diagram in tutorial slides as your guide for the intuition. I personally find it useful.