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

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
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 pnpnpcnph
0
votes
0
answers
1
Proving a problem as NPcomplete.
According to this article, A problem X can be proved to be NPcomplete if an already existing NPcomplete problem (say Y) can be polynomialtime reduced to current problem X. The problem also needs to be NP. Now my question is: Do we also ... have to be only one way to prove a problem is NPcomplete? PS: I have already asked this question in cs.stackexchange
asked
Jun 14
in
Theory of Computation
by
commenter commenter
(
321
points)

44
views
pnpnpcnph
theoryofcomputation
0
votes
0
answers
2
Is each and every NP complete problem (polynomially) reduced to each and every another NP complete problem?
asked
Jun 13
in
Theory of Computation
by
commenter commenter
(
321
points)

42
views
pnpnpcnph
theoryofcomputation
timecomplexity
0
votes
0
answers
3
SelfDoubt(PNP class)
$1)$ If the complement of NPComplete problem is in NP, then can we also say , for this case complement of NP problem is in NPComplete ? $2)$ If the complement of NPComplete problem is in CoNP, then can we also say, for this case complement of CoNP problem is in NPComplete?
asked
Apr 22
in
Theory of Computation
by
srestha
Veteran
(
113k
points)

70
views
pnpnpcnph
theoryofcomputation
+1
vote
1
answer
4
P and NP Question doubt
What will be the answer to this question? L’ is the complement of language L belongs to NP does not always imply that L’ belongs to NP L’ belongs to P both a and b
asked
Apr 20
in
Theory of Computation
by
Rhythm
(
189
points)

205
views
pnpnpcnph
+1
vote
1
answer
5
If there is an $\rm NP$complete language $L$ whose complement is in $\rm NP$, then...
asked
Apr 20
in
Theory of Computation
by
Rhythm
(
189
points)

102
views
theoryofcomputation
timecomplexity
pnpnpcnph
+1
vote
1
answer
6
TIFR2019B7
A formula is said to be a $3$CFformula if it is a conjunction (i.e., an AND) of clauses, and each clause has at most $3$ literals. Analogously, a formula is said to be a $3$DFformula if it is a disjunction (i.e., an OR) of clauses of at most $3$ literals each. ... $\text{3DFSAT}$ is NPcomplete Neither $\text{3CFSAT}$ nor $\text{3DFSAT}$ are in P
asked
Dec 18, 2018
in
Algorithms
by
Arjun
Veteran
(
416k
points)

151
views
tifr2019
algorithms
pnpnpcnph
0
votes
1
answer
7
Undirected Graph  Hamiltonian Cycle  NP Complete?
All the places where I have read the HamCycle problem, the graph used is directed. Is the problem of finding HamCycle on an undirected graph also NPComplete or not?
asked
Nov 30, 2018
in
Algorithms
by
gmrishikumar
Active
(
1.9k
points)

101
views
graphtheory
cycle
theoryofcomputation
pnpnpcnph
grapg
npcomplete
0
votes
0
answers
8
Decidable
All $P$, $NP$ and $NPC$ problems are turing decidable problems. $CFLs$ are in $NP$ area and $CFL's$ are not closed under intersection and complementation. So does it mean that $CFL's$ are undecidable under intersection and complementation. If $CFL$ is undecidable on intersection and complementation then how $NP$ problems can be turing decidable?
asked
Jun 18, 2018
in
Theory of Computation
by
!KARAN
Active
(
1.9k
points)

51
views
theoryofcomputation
pnpnpcnph
decidability
0
votes
1
answer
9
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, 2018
in
Theory of Computation
by
rahul sharma 5
Boss
(
24.5k
points)

233
views
pnpnpcnph
theoryofcomputation
0
votes
1
answer
10
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, 2018
in
Theory of Computation
by
Harsh Kumar
Active
(
1.2k
points)

151
views
pnpnpcnph
theoryofcomputation
+3
votes
1
answer
11
CMI2017A10
We have constructed a polynomial time reduction from problem $A$ to problem $B$. Which of the following is a valid inference? If the best algorithm for $B$ takes exponential time, then there is no polynomial time algorithm for $A$ ... don't know whether there is a polynomial time algorithm for $B$, then there cannot be a polynomial time algorithm for $A$.
asked
Feb 5, 2018
in
Algorithms
by
Tesla!
Boss
(
18k
points)

293
views
cmi2017
algorithms
reduction
pnpnpcnph
+2
votes
0
answers
12
Self Doubt IMP
Can Anyone please post the diagram which describes the relation between P, NP, NPSPACE, NPHard, EXPONENTIAL TIME etc.
asked
Jan 15, 2018
in
Algorithms
by
ankit_thawal
Active
(
1.4k
points)

42
views
pnpnpcnph
+5
votes
0
answers
13
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, 2018
in
Theory of Computation
by
humblefool
Junior
(
927
points)

196
views
pnpnpcnph
theoryofcomputation
syllabus
0
votes
0
answers
14
did P and NP is still in the syllabus? @ COMPUTABILITY AND COMPLEXITY{TOC}
did P and NP is still in the syllabus? @ COMPUTABILITY AND COMPLEXITY{TOC}
asked
Dec 25, 2017
in
Theory of Computation
by
hacker16
Active
(
2.7k
points)

132
views
syllabus
pnpnpcnph
theoryofcomputation
+3
votes
1
answer
15
TIFR2018B15
$G$ respresents an undirected graph and a cycle refers to a simple cycle (no repeated edges or vertices). Define the following two languages. $SCYCLE=\{(G,k)\mid G \text{ contains a cycle of length at most k}\}$ ... $SCYCLE \leq_{p} LCYCLE$ (i.e, there is a polynomial time manytoone reduction from $SCYCLE$ to $LCYCLE$).
asked
Dec 10, 2017
in
Algorithms
by
Arjun
Veteran
(
416k
points)

258
views
tifr2018
algorithms
pnpnpcnph
nongate
+1
vote
1
answer
16
Self doubt in terminologies and turing machine
1) I know that turing decidable means recursive language. But does is also means its decidable? So basically i want to know if REC imples decidability and RE implies undecidability or not. I got confused with word decidable in " ... same expressive power why can't we use DTM in NP decision problems? Thanks for being patient and reading doubt.
asked
Nov 29, 2017
in
Theory of Computation
by
♥_Less
Junior
(
901
points)

177
views
theoryofcomputation
turingmachine
decidability
selfdoubt
pnpnpcnph
0
votes
2
answers
17
having confusion in P ,Np,NP hard and Np completness
what i have tried to get out the conslusion for P problem is that P problem These are set of those yes/no problems which can solved using polynomic time complexity algroithms. For example if are asked to Compare or sort then numbers.Then using loop we ... .hence this Np problem is now P problem Am i correct with these two terms ????????????????
asked
Mar 26, 2017
in
Algorithms
by
LavTheRawkstar
Active
(
3.7k
points)

600
views
pnpnpcnph
0
votes
0
answers
18
Virtual Gate Test Series: Algorithms  NP Class
asked
Dec 30, 2016
in
Algorithms
by
firki lama
Junior
(
655
points)

47
views
algorithms
pnpnpcnph
virtualgatetestseries
0
votes
1
answer
19
Virtual Gate Test Series: Algorithms  NP Complete Problem
asked
Dec 30, 2016
in
Algorithms
by
firki lama
Junior
(
655
points)

119
views
algorithms
pnpnpcnph
virtualgatetestseries
+3
votes
0
answers
20
TIFR2016B8
Consider the following language $\mathsf{PRIMES} = \Biggl\{ \underbrace{111 \dots 11}_{p \: \text{ times} } : \: p \: \text{ is prime } \Biggl\}$ Then, which of the following is TRUE? $\mathsf{PRIMES}$ is regular $\mathsf{PRIMES}$ ... $\mathsf{PRIMES}$ is context free but not regular $\mathsf{PRIMES}$ is NPcomplete and P $\neq$ NP
asked
Dec 29, 2016
in
Others
by
jothee
Veteran
(
99.2k
points)

129
views
tifr2016
decidability
pnpnpcnph
+2
votes
1
answer
21
TIFR2016B3
Assume $P \neq NP$. Which of the following is not TRUE? 2SAT in NP 2SAT in coNP 3SAT is polynmialtime reducible to 2SAT 4SAT is polynmialtime reducible to 3SAT 2SAT in P
asked
Dec 28, 2016
in
Others
by
jothee
Veteran
(
99.2k
points)

94
views
tifr2016
pnpnpcnph
3sat
2sat
0
votes
0
answers
22
MadeEasy Subject Test: Theory of Computation  P Np Npc Nph
Let L1 = Φ and L2 = Σ*. Then which of the following is correct? L1 is NPcomplete, L2 is not NPcomplete L1 is not NPcomplete, L2 is NPcomplete Both L1 and L2 are NPcomplete Neither L1 nor L2 is NPcomplete I know ... my query is in solution they are saying that L1 and L2 are P problems but L1 and L2 are undecidable how can they be P?
asked
Dec 28, 2016
in
Theory of Computation
by
Pankaj Joshi
Active
(
2.6k
points)

64
views
madeeasytestseries
theoryofcomputation
pnpnpcnph
+3
votes
1
answer
23
TIFR2017B15
A multivariate polynomial in $n$ variables with integer coefficients has a binary root if it is possible to assign each variable either 0 or 1, so that the polynomial evaluates to 0. For example, the multivariate polynomial $2x_1^3 x_1x_2+2$ ... time is NPhard, but not in NP is in NP, but not in P and not NPhard is both in NP and NPhard
asked
Dec 23, 2016
in
Algorithms
by
jothee
Veteran
(
99.2k
points)

261
views
tifr2017
algorithms
pnpnpcnph
+1
vote
1
answer
24
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}$ ... ? Choose 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
(
99.2k
points)

252
views
tifr2017
algorithms
pnpnpcnph
0
votes
1
answer
25
MadeEasy Test Series: Algorithms  P Np Npc Nph
Q. consider the following problem: a) Eulerian path b) 2 SAT c) Constraint reachibilty d)graph coloring number of problem which is polynomial solvable?? i am get only b (2SAT) somy answer is 1 but answer given 2 here also eulerian path ?? how to appraoch these type of question Plz explain??
asked
Nov 20, 2016
in
Theory of Computation
by
Hradesh patel
Loyal
(
6.2k
points)

95
views
madeeasytestseries
algorithms
pnpnpcnph
0
votes
1
answer
26
Kerala PSC AP Exam
A problem in NP is NP complete if A) Some problem in NP can be reduced to it in polynomial time B) The 3SAT problem can be reduced to it in polynomial time C) It can be reduced to any other problems in NP in polynomial time D) It can be reduced to the 3SAT problem in polynomial time
asked
Oct 27, 2016
in
Algorithms
by
Sankaranarayanan P.N
Boss
(
11k
points)

155
views
pnpnpcnph
+1
vote
1
answer
27
UGCNETDec2014III33
We can show that the clique problem is $NP$hard by proving that CLIQUE $\leq$ P 3CNF_SAT CLIQUE $\leq$ P VERTEX_COVER CLIQUE $\leq$ P SUBSET_SUM None of the above
asked
Jul 28, 2016
in
Algorithms
by
makhdoom ghaya
Boss
(
29.6k
points)

964
views
ugcnetdec2014iii
algorithms
pnpnpcnph
+6
votes
2
answers
28
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
(
99.2k
points)

285
views
cmi2015
algorithms
pnpnpcnph
+1
vote
1
answer
29
What is the time complexity of Binary Knapsack?
I was reading some of the notes (made easy and ACE) and noticed that some teacher have taught that time complexity for Binary Knapsack O(2^(n/2)). which can not be reduced further. but What I have seen here that in ... techniques? Put some light, Am I missing something. Should I stop seeing those notes which people have posted over the internet.
asked
May 23, 2016
in
Algorithms
by
rude
Boss
(
35.5k
points)

1.2k
views
timecomplexity
dynamicprogramming
pnpnpcnph
Page:
1
2
next »
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
ISI MTECH CS 2019 INTERVIEW EXPERIENCE
IIT HYDERABAD MTECH TA INTERVIEW EXPERIENCE
How to prepare for GATE with a fulltime job??
Interview Experience at IISc
All subject Gate notes from Standard Books!!
Follow @csegate
Recent questions tagged pnpnpcnph
Recent Blog Comments
Refund time depends on the payment mode ...
@Arjun Sir , when can i expect my refund in the...
This book is returned you can enable a pay now...
@Pranavcool The book stocks are over and no one...
@Lokesh Thats unfortunate. I have refunded you....
49,823
questions
54,822
answers
189,572
comments
81,056
users