Exams › GATE › Technical

Which of the following statements are TRUE ? 1. The problem of determining whether there exists a cycle in an undirected graph is in P. 2. The problem of determining whether there exists a cycle in a directed graph is in NP. 3. If a problem A is NP-Complete, there exists a non-deterministic polynomial time algorithm to solve A.

1. 1, 2 and 3
2. 1 and 2 only
3. 2 and 3 only
4. 1 and 3 only

Correct answer: 1, 2 and 3

Solution

All three statements are true: the cycle detection problem in undirected graphs can be solved in polynomial time (thus in P), the directed graph cycle problem is verifiable in polynomial time (hence in NP), and NP-Complete problems are defined by the existence of non-deterministic polynomial time algorithms.

Related GATE Technical questions

• The truth table X Y f(X,Y) 0 0 0 0 1 0 1 0 1 1 1 1 represents the Boolean function
• The decimal value 0.5 in IEEE single precision floating point representation has
• A process executes the code fork(); fork(); fork(); The total number of child processes created is
• The protocol data unit (PDU) for the application layer in the Internet stack is
• Which of the following problems are decidable? 1) Does a given program ever produce an output? 2) If L is a context-free language, then is L̄ also context-free? 3) If L is a regular language, then is L̄ also regular? 4) If L is a recursive language, then is L̄ also recursive?
• A binary operation ⊕ on a set of integers is defined as x ⊕ y = x² × y². Which one of the following statements is TRUE about ⊕?

⚔️ Practice GATE Technical free + battle 1v1 →