in Algorithms recategorized ago by
36 views
1 vote
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?

  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.
in Algorithms recategorized ago by
by
36 views

Please log in or register to answer this question.

Answer:

Related questions