recategorized by
356 views
1 votes
1 votes

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.
recategorized by

Please log in or register to answer this question.

Answer:

Related questions

1 votes
1 votes
1 answer
3
admin asked Sep 1, 2022
797 views
Consider the problem of sorting $n$ single digit integers (base $10$). This problem can be solved in time$O(n \log n)$ but not $O(n \log \log n)$$O(n \log \log n)$ but no...