The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
Facebook Login
Google Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
All Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Recent questions tagged npcompleteness
0
votes
1
answer
1
Np Hard Problems
Are NPHard problems Semi decidable or Decidable or not even semidecidable? I know NP class is decidable as there is polynomial time NTM.But in the following figure in case there are some NP hard problems that are lying outside of NP.Problems which are NPhard but not NPC.Can these also be solved in polynomial time by NTM?
asked
Apr 16
in
Theory of Computation
by
rahul sharma 5
Boss
(
24.1k
points)

113
views
pnpnpcnph
theoryofcomputation
npcompleteness
0
votes
1
answer
2
Npcomplete Problems
I know that NPcomplete problems are the hardest NP problems and every NP problem can be reduced NPComplete problems in polynomial time. Now, it is said that all NP problems can be solved in Nondeterministic polynomial time, so is it true that ALL NPCOMPLETE PROBLEMS CAN BE SOLVED IN NONDETERMINISTIC POLYNOMIAL TIME ?
asked
Mar 20
in
Theory of Computation
by
Harsh Kumar
(
181
points)

43
views
npcompleteness
pnpnpcnph
theoryofcomputation
+2
votes
0
answers
3
Self Doubt IMP
Can Anyone please post the diagram which describes the relation between P, NP, NPSPACE, NPHard, EXPONENTIAL TIME etc.
asked
Jan 15
in
Algorithms
by
ankit_thawal
Active
(
2.1k
points)

32
views
npcompleteness
+3
votes
1
answer
4
Query regarding P NP
I know this questions is already asked but no answers are yet given IS P NP STILL PRESENT IN GATE 2018 SYLLABUS? The Official Syllabus EXCLUDES those topics and according to https://gatecse.in/gatecse2016syllabus/ , the P NP is NOT THERE. But ... verify it. And please dont say, "it is better to read" because although knowledge is good but time is precious :)
asked
Jan 6
in
Theory of Computation
by
humblefool
Junior
(
937
points)

59
views
pnpnpcnph
theoryofcomputation
syllabus
npcompleteness
+1
vote
1
answer
5
TIFR2017B2
Consider the following statements: Checking if a given $undirected$ graph has a cycle is in $\mathsf{P}$ Checking if a given $undirected$ graph has a cycle is in $\mathsf{NP}$ Checking if a given $directed$ graph has a cycle is in $\mathsf{P}$ Checking if a given $directed$ ... from the following options. Only i and ii Only ii and iv Only ii, iii, and iv Only i, ii and iv All of them
asked
Dec 23, 2016
in
Algorithms
by
jothee
Veteran
(
98.5k
points)

173
views
tifr2017
algorithms
npcompleteness
+6
votes
2
answers
6
CMI2015A06
Suppose we have constructed a polynomial time reduction from problem $A$ to problem $B$. Which of the following can we infer from this fact? If the best algorithm for $B$ takes exponential time, there is no polynomial time algorithm for $A$. If the best ... we don't know whether there is a polynomial time algorithm for $B$, there cannot be a polynomial time algorithm for $A$.
asked
May 27, 2016
in
Algorithms
by
jothee
Veteran
(
98.5k
points)

152
views
cmi2015
algorithms
npcompleteness
+4
votes
1
answer
7
TIFR2013B7
Which of the following is not implied by $P=NP$? $3$SAT can be solved in polynomial time. Halting problem can be solved in polynomial time. Factoring can be solved in polynomial time. Graph isomorphism can be solved in polynomial time. Travelling salesman problem can be solved in polynomial time.
asked
Nov 6, 2015
in
Algorithms
by
makhdoom ghaya
Boss
(
40k
points)

220
views
tifr2013
algorithms
npcompleteness
+4
votes
1
answer
8
TIFR2011B37
Given an integer $n\geq 3$, consider the problem of determining if there exist integers $a,b\geq 2$ such that $n=a^{b}$. Call this the forward problem. The reverse problem is: given $a$ and $b$, compute $a^{b}$ (mod b). Note that the input ... be solved in polynomial time, however the forward problem is $NP$hard. Both the forward and reverse problem are $NP$hard. None of the above.
asked
Oct 25, 2015
in
Algorithms
by
makhdoom ghaya
Boss
(
40k
points)

252
views
tifr2011
algorithms
npcompleteness
+6
votes
3
answers
9
TIFR2010B39
Suppose a language $L$ is $\mathbf{NP}$ complete. Then which of the following is FALSE? $L \in \mathbf{NP}$ Every problem in $\mathbf{P}$ is polynomial time reducible to $L$. Every problem in $\mathbf{NP}$ is polynomial time reducible to $L$. The Hamilton cycle problem is polynomial time reducible to $L$. $\mathbf{P} \neq \mathbf{NP}$ and $L \in \mathbf{P}$.
asked
Oct 11, 2015
in
Algorithms
by
makhdoom ghaya
Boss
(
40k
points)

327
views
tifr2010
algorithms
npcompleteness
+10
votes
1
answer
10
GATE201318
Which of the following statements are TRUE? The problem of determining whether there exists a cycle in an undirected graph is in $P$. The problem of determining whether there exists a cycle in an undirected graph is in $NP$. If a problem A is $NPComplete$, there exists a nondeterministic polynomial time algorithm to solve $A$ 1, 2 and 3 1 and 2 only 2 and 3 only 1 and 3 only
asked
Sep 23, 2014
in
Theory of Computation
by
Arjun
Veteran
(
348k
points)

1.2k
views
gate2013
theoryofcomputation
npcompleteness
normal
+7
votes
1
answer
11
GATE200558
Consider the following two problems on undirected graphs: $\alpha$: Given $G(V, E)$, does $G$ have an independent set of size V  $4$? $\beta$: Given $G(V, E)$, does $G$ have an independent set of size $5$? Which one of the following is TRUE? $\alpha$ is in ... $\alpha$ is NPcomplete and $\beta$ is in P Both $\alpha$ and $\beta$ are NPcomplete Both $\alpha$ and $\beta$ are in P
asked
Sep 22, 2014
in
Theory of Computation
by
Kathleen
Veteran
(
59.4k
points)

917
views
gate2005
theoryofcomputation
npcompleteness
normal
+5
votes
1
answer
12
GATE200914
Let $\pi_A$ be a problem that belongs to the class NP. Then which one of the following is TRUE? There is no polynomial time algorithm for $\pi_A$. If $\pi_A$ can be solved deterministically in polynomial time, then P = NP. If $\pi_A$ is NPhard, then it is NPcomplete. $\pi_A$ may be undecidable.
asked
Sep 22, 2014
in
Theory of Computation
by
Kathleen
Veteran
(
59.4k
points)

1.1k
views
gate2009
theoryofcomputation
npcompleteness
+9
votes
7
answers
13
GATE200430, ISRO201710
The problem $3$SAT and $2$SAT are both in $P$ both $NP$ complete $NP$complete and in $P$ respectively undecidable and $NP$ complete respectively
asked
Sep 19, 2014
in
Algorithms
by
Kathleen
Veteran
(
59.4k
points)

3.5k
views
gate2004
algorithms
npcompleteness
easy
isro2017
+4
votes
2
answers
14
GATE200631
Let SHAM$_3$ be the problem of finding a Hamiltonian cycle in a graph $G=(V,E)$ with $V$ divisible by $3$ and DHAM$_3$ be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true? Both DHAM$_3$ and ... NPhard SHAM$_3$ is NPhard, but DHAM$_3$ is not DHAM$_3$ is NPhard, but SHAM$_3$ is not Neither DHAM$_3$ nor SHAM$_3$ is NPhard
asked
Sep 18, 2014
in
Theory of Computation
by
Rucha Shelke
Active
(
3.7k
points)

816
views
gate2006
theoryofcomputation
npcompleteness
normal
+14
votes
4
answers
15
GATE200616, ISRODEC201727
Let S be an NPcomplete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomialtime reducible to R. Which one of the following statements is true? R is NPcomplete R is NPhard Q is NPcomplete Q is NPhard
asked
Sep 17, 2014
in
Algorithms
by
Rucha Shelke
Active
(
3.7k
points)

2.7k
views
gate2006
algorithms
npcompleteness
normal
isrodec2017
+10
votes
2
answers
16
GATE200312
Ram and Shyam have been asked to show that a certain problem $\Pi$ is NPcomplete. Ram shows a polynomial time reduction from the $3$SAT problem to $\Pi$, and Shyam shows a polynomial time reduction from $\Pi$ to $3$SAT. Which of the following can be inferred from these ... not NPcomplete $\Pi$ is in NP, but is not NPcomplete $\Pi$ is NPcomplete $\Pi$ is neither NPhard, nor in NP
asked
Sep 16, 2014
in
Algorithms
by
Kathleen
Veteran
(
59.4k
points)

1.5k
views
gate2003
algorithms
npcompleteness
normal
+5
votes
2
answers
17
GATE199202,vi
$0$2. Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: (vi) Which of the following problems is not $NP$hard? Hamiltonian circuit problem The $0/1$ Knapsack problem Finding biconnected components of a graph The graph coloring problem
asked
Sep 13, 2014
in
Algorithms
by
Kathleen
Veteran
(
59.4k
points)

720
views
gate1992
npcompleteness
algorithms
+9
votes
1
answer
18
GATE200844
The subsetsum 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 ... polynomial time when the input is encoded in binary The subset sum problem belongs to the class NP The subset sum problem is NPhard
asked
Sep 12, 2014
in
Algorithms
by
Kathleen
Veteran
(
59.4k
points)

2.3k
views
gate2008
algorithms
npcompleteness
normal
+15
votes
4
answers
19
GATE20124
Assuming $P \neq NP$, which of the following is TRUE? $NP \ complete = NP$ $NPcomplete \cap P = \phi$ $NPhard = NP$ $P = NPcomplete$
asked
Aug 5, 2014
in
Theory of Computation
by
gatecse
Boss
(
18k
points)

1.9k
views
gate2012
theoryofcomputation
npcompleteness
To see more, click for the
full list of questions
or
popular tags
.
Quick search syntax
tags
tag:apple
author
user:martin
title
title:apple
content
content:apple
exclude
tag:apple
force match
+apple
views
views:100
score
score:10
answers
answers:2
is accepted
isaccepted:true
is closed
isclosed:true
Recent Posts
IIIT Hyderabad Interview Experience
The GATE journey
BARC Interview Experience 15th June 2018
COAP Admission and IITD, IITK Interview Experience 2018
MS Interview Experience at IITK
Follow @csegate
Gatecse
Recent questions tagged npcompleteness
Recent Blog Comments
Congratulations Priyendu, thanks for sharing the ...
Most probably IITK. Analyzed a lot and finally ...
Congratulations! Which college are you aiming for ...
yes. I'm joining bits goa. I'm from goa also so ...
You did this in final year or with job?
36,132
questions
43,577
answers
123,847
comments
42,815
users