Question

Which of the following statements are TRUE?

o The problem of determining whether there exists a cycle in an undirected graph is in P.
o The problem of determining whether there exists a cycle in an undirected graph is in NP.
o If a problem A is NP-Complete, there exists a non-deterministic polynomial time algorithm to solve A.

Answer 1

The problem of determining whether there exists a cycle in an undirected graph is in NP, and if a problem is NP-Complete, there exists a non-deterministic polynomial time algorithm to solve it.

Step-by-step explanation:

The correct statements are:

1. The problem of determining whether there exists a cycle in an undirected graph is in NP.
2. If a problem A is NP-Complete, there exists a non-deterministic polynomial time algorithm to solve A.

The first statement is false because the problem of determining whether there exists a cycle in an undirected graph is not in P. It is actually one of the classic examples of an NP-Complete problem.

The second statement is true. If a problem A is NP-Complete, it means that it is one of the hardest problems in NP and that any problem in NP can be reduced to A in polynomial time. Therefore, there must exist a non-deterministic polynomial time algorithm to solve A.