P-NP Theory

 Question 1
The problem 3-SAT and 2-SAT are
 A both in P B both NP complete C NP -complete and in P respectively D undecidable and NP complete respectively
ISRO CSE 2017   Algorithm
Question 1 Explanation:
 Question 2
Language $L_{1}$ is polynomial time reducible to language $L_{2}$. Language $L_{3}$ is polynomial time reducible to $L_{2}$, which in turn is polynomial time reducible to language $L_{4}$. Which of the following is/are true?
I. if $L_{4} \in P$, then $L_{2} \in P$
II. if $L_{1} \in P$ or $L_{3} \in P$, then $L_{2} \in P$
III. $L_{1} \in P$, if and only if $L_{3} \in P$
IV. if $L_{4} \in P$, then $L_{1} \in P$ and $L_{3} \in P$
 A II only B III only C I and IV only D I only
GATE CSE 2015 SET-3   Algorithm
Question 2 Explanation:
 Question 3
Consider two decision problems Q1,Q2 such that Q1 reduces in polynomial time to 3-SAT and 3-SAT reduces in polynomial time to Q2. Then which one of the following is consistent with the above statement?
 A Q1 is in NP, Q2 is NP hard. B Q2 is in NP, Q1 is NP hard C Both Q1 and Q2 are in NP . D Both Q1 and Q2 are NP hard
GATE CSE 2015 SET-2   Algorithm
Question 3 Explanation:
 Question 4
Consider the decision problem 2CNFSAT defined as follows:
{ $\phi$ | $\phi$ is a satisfiable propositional formula in CNF with at most two literal per clause}
For example, $\phi =(x_{1} \vee x_{2}) \wedge (x_{1} \vee \bar{x_{3}}) \wedge (x_{2} \vee x_{4})$ is a Boolean formula and it is in 2CNFSAT.
The decision problem 2CNFSAT is
 A NP-Complete B solvable in polynomial time by reduction to directed graph reachability. C solvable in constant time since any input instance is satisfiable D NP-hard, but not NP-complete
GATE CSE 2014 SET-3   Algorithm
Question 4 Explanation:
 Question 5
Suppose a polynomial time algorithm is discovered that correctly computes the largest clique in a given graph. In this scenario, which one of the following represents the correct Venn diagram of the complexity classes P, NP and NP Complete (NPC)?
 A A B B C C D D
GATE CSE 2014 SET-1   Algorithm
Question 5 Explanation:
 Question 6
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 an undirected graph is in NP.
3. If a problem A is NP-Complete, there exists a non-deterministic polynomial time algorithm to solve A.
 A 1, 2 and 3 B 1 and 2 only C 2 and 3 only D 1 and 3 only
GATE CSE 2013   Algorithm
Question 6 Explanation:
 Question 7
Assuming P $\neq$ NP, which of the following is TRUE?
 A NP-complete = NP B NP-complete $\cap$ P = $\phi$ C NP-hard = NP D P = NP-complete
GATE CSE 2012   Algorithm
Question 7 Explanation:
 Question 8
Let $\pi _{A}$ be a problem that belongs to the class NP. Then which one of the following is TRUE?
 A There is no polynomial time algorithm for $\pi _{A}$. B If $\pi _{A}$ can be solved deterministically in polynomial time, then P = NP. C If $\pi _{A}$ is NP-hard, then it is NP-complete. D $\pi _{A}$ may be undecidable
GATE CSE 2009   Algorithm
Question 8 Explanation:
 Question 9
For problems X and Y, Y is NP-complete and X reduces to Y in polynomial time. Which of the following is TRUE?
 A If X can be solved in polynomial time, then so can Y B X is NP-complete C X is NP-hard D X is in NP, but not necessarily NP-complete
GATE IT 2008   Algorithm
Question 9 Explanation:
 Question 10
The subset-sum problem is defined as follows: Given a set S of n positive integers and a positive integer W, determine whether there is a subset of S Whose elements sum to W.
An algorithm Q solves this problem in O(nW) time. Which of the following statements is false?
 A Q solves the subset-sum problem in polynomial time when the input is encoded in unary B Q solves the subset-sum problem in polynomial time when the input is encoded in binary C The subset sum problem belongs to the class NP D The subset sum problem is NP-hard
GATE CSE 2008   Algorithm
Question 10 Explanation:
There are 10 questions to complete.