Dark Mode

86 views

1 vote

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?

- $\text{A1}$ implies $\text{A2}$ and $\text{A2}$ implies $\text{A1}$
- $\text{A1}$ implies $\text{A2}$ and $\text{A2}$ does not imply $\text{A1}$
- $\text{A1}$ does not imply $\text{A2}$ and $\text{A2}$ implies $\text{A1}$
- $\text{A1}$ does not imply $\text{A2}$ and $\text{A2}$ does not imply $\text{A1}$
- None of the above.