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
Recent questions tagged pnpnpcnph
0
votes
2
answers
1
Understanding Nphard
I am having difficulty in understanding np and nphard topic in algorithms. If someone can provide some good source to learn about it in easy manner it would be a real help. Thank you!
asked
Sep 22, 2019
in
Algorithms
by
luc_Bloodstone
(
91
points)

110
views
pnpnpcnph
algorithms
0
votes
1
answer
2
CMI2019A8
We have constructed a polynomial time reduction from problem A to problem B. Which of the following is not a possible scenario? We know of polynomial time algorithms for both A and B. We only know of exponential time algorithms for both A and B. We only ... polynomial time algorithm for B. We only know an exponential time algorithm for B, but we have a polynomial time algorithm for A.
asked
Sep 13, 2019
in
Theory of Computation
by
gatecse
Boss
(
17.5k
points)

35
views
cmi2019
reduction
pnpnpcnph
0
votes
0
answers
3
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, 2019
in
Theory of Computation
by
commenter commenter
Active
(
1.6k
points)

65
views
pnpnpcnph
theoryofcomputation
0
votes
0
answers
4
Is each and every NP complete problem (polynomially) reduced to each and every another NP complete problem?
asked
Jun 13, 2019
in
Theory of Computation
by
commenter commenter
Active
(
1.6k
points)

49
views
pnpnpcnph
theoryofcomputation
timecomplexity
0
votes
0
answers
5
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, 2019
in
Theory of Computation
by
srestha
Veteran
(
119k
points)

80
views
pnpnpcnph
theoryofcomputation
+1
vote
1
answer
6
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, 2019
in
Theory of Computation
by
Rhythm
(
195
points)

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

124
views
theoryofcomputation
timecomplexity
pnpnpcnph
+1
vote
1
answer
8
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
(
431k
points)

215
views
tifr2019
algorithms
pnpnpcnph
0
votes
1
answer
9
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
(
2.2k
points)

120
views
graphtheory
cycle
theoryofcomputation
pnpnpcnph
grapg
npcomplete
0
votes
0
answers
10
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
(
2.4k
points)

52
views
theoryofcomputation
pnpnpcnph
decidability
0
votes
1
answer
11
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
(
25.6k
points)

264
views
pnpnpcnph
theoryofcomputation
0
votes
1
answer
12
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.3k
points)

181
views
pnpnpcnph
theoryofcomputation
+3
votes
1
answer
13
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
(
18.4k
points)

334
views
cmi2017
algorithms
reduction
pnpnpcnph
+2
votes
0
answers
14
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)

49
views
pnpnpcnph
+5
votes
0
answers
15
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
(
963
points)

230
views
pnpnpcnph
theoryofcomputation
syllabus
0
votes
0
answers
16
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)

145
views
syllabus
pnpnpcnph
theoryofcomputation
+3
votes
1
answer
17
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
(
431k
points)

307
views
tifr2018
algorithms
pnpnpcnph
nongate
+1
vote
1
answer
18
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
(
939
points)

214
views
theoryofcomputation
turingmachine
decidability
selfdoubt
pnpnpcnph
0
votes
2
answers
19
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.8k
points)

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

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

127
views
algorithms
pnpnpcnph
virtualgatetestseries
+3
votes
0
answers
22
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
(
105k
points)

147
views
tifr2016
decidability
pnpnpcnph
+2
votes
1
answer
23
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
(
105k
points)

105
views
tifr2016
pnpnpcnph
3sat
2sat
0
votes
0
answers
24
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.7k
points)

68
views
madeeasytestseries
theoryofcomputation
pnpnpcnph
+4
votes
1
answer
25
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
(
105k
points)

319
views
tifr2017
algorithms
pnpnpcnph
+2
votes
1
answer
26
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
(
105k
points)

307
views
tifr2017
algorithms
pnpnpcnph
0
votes
1
answer
27
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.5k
points)

101
views
madeeasytestseries
algorithms
pnpnpcnph
0
votes
1
answer
28
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)

162
views
pnpnpcnph
+1
vote
1
answer
29
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
(
30.8k
points)

1k
views
ugcnetdec2014iii
algorithms
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
ISRO CSE 2020 PAPER ANALYSE
BARC OCES/DGFS 2020
ISI CMI PDF by GATE Overflow
Calculus Important Points
Management Trainee Recruitment COAL INDIA 2020
Follow @csegate
Recent questions tagged pnpnpcnph
Recent Blog Comments
@nkg_master9  For getting selected for the...
Nowhere it's mentioned.
@bond  Is it mentioned that you have to score at...
I think cutoff won't cross 85
Cut off will be between 95115 not more than that.
50,737
questions
57,378
answers
198,522
comments
105,314
users