Which of the following statements are TRUE? The problem of determining whether…

Concept

Two complexity facts govern this problem. First, the inclusion P ⊆ NP always holds: any decision problem solvable by a deterministic polynomial-time algorithm is also solvable by a non-deterministic one (the machine simply never uses its guessing power), so membership in P implies membership in NP. Second, by definition NP is exactly the class of decision problems for which a non-deterministic Turing machine runs in polynomial time, and every NP-Complete problem lies inside NP — so an NP-Complete problem necessarily has a non-deterministic polynomial-time algorithm.

Applying it to each statement

1. “Undirected-graph cycle detection is in P.” A single depth-first search (or a union-find pass over the edges) detects a cycle in O(V + E) time — a deterministic polynomial-time procedure. Hence the problem is in P. TRUE.

2. “The same problem is in NP.” Since it is in P and P ⊆ NP, it is automatically in NP (a verifier can also be built in polynomial time). TRUE.

3. “An NP-Complete problem A has a non-deterministic polynomial-time algorithm.” Every NP-Complete problem is, by definition, a member of NP, and NP is precisely the set of problems decidable by a non-deterministic polynomial-time machine. So such an algorithm exists. TRUE.

Cross-check

All three statements hold, so the true set is exactly {1, 2, 3}. A common trap is to think NP means “hard / not in P”; in fact P ⊆ NP, so a polynomial problem being in NP is not a contradiction, and “non-deterministic polynomial time” is simply the defining property of NP, not a claim about tractability.