86 views

Consider the assertions

$\text{(A1)}$ Given a directed graph $G$ with positive weights on the edges, two special vertices $s$ and $t$, and an integer $k$ - it is $\text{NP}$-complete to determine if $G$ has an $s- t$ path of length at most $k$.

$\text{(A2)}$ $\mathrm{P}=\mathrm{NP}$

Then, which of the following is true?

1. $\text{A1}$ implies $\text{A2}$ and $\text{A2}$ implies $\text{A1}$
2. $\text{A1}$ implies $\text{A2}$ and $\text{A2}$ does not imply $\text{A1}$
3. $\text{A1}$ does not imply $\text{A2}$ and $\text{A2}$ implies $\text{A1}$
4. $\text{A1}$ does not imply $\text{A2}$ and $\text{A2}$ does not imply $\text{A1}$
5. None of the above.

1 vote