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
in
Algorithms
by
luc_Bloodstone
(
89
points)

93
views
pnpnpcnph
algorithms
0
votes
0
answers
2
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
Active
(
1.2k
points)

59
views
pnpnpcnph
theoryofcomputation
0
votes
0
answers
3
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
Active
(
1.2k
points)

46
views
pnpnpcnph
theoryofcomputation
timecomplexity
0
votes
0
answers
4
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
(
117k
points)

77
views
pnpnpcnph
theoryofcomputation
+1
vote
1
answer
5
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
(
195
points)

216
views
pnpnpcnph
+1
vote
1
answer
6
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
(
195
points)

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

200
views
tifr2019
algorithms
pnpnpcnph
0
votes
1
answer
8
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.1k
points)

110
views
graphtheory
cycle
theoryofcomputation
pnpnpcnph
grapg
npcomplete
0
votes
0
answers
9
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.2k
points)

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

248
views
pnpnpcnph
theoryofcomputation
0
votes
1
answer
11
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)

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

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

44
views
pnpnpcnph
+5
votes
0
answers
14
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
(
939
points)

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

144
views
syllabus
pnpnpcnph
theoryofcomputation
+3
votes
1
answer
16
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
(
425k
points)

297
views
tifr2018
algorithms
pnpnpcnph
nongate
+1
vote
1
answer
17
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
(
931
points)

185
views
theoryofcomputation
turingmachine
decidability
selfdoubt
pnpnpcnph
0
votes
2
answers
18
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)

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

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

125
views
algorithms
pnpnpcnph
virtualgatetestseries
+3
votes
0
answers
21
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)

145
views
tifr2016
decidability
pnpnpcnph
+2
votes
1
answer
22
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)

104
views
tifr2016
pnpnpcnph
3sat
2sat
0
votes
0
answers
23
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)

68
views
madeeasytestseries
theoryofcomputation
pnpnpcnph
+4
votes
1
answer
24
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)

310
views
tifr2017
algorithms
pnpnpcnph
+1
vote
1
answer
25
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)

294
views
tifr2017
algorithms
pnpnpcnph
0
votes
1
answer
26
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.3k
points)

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

156
views
pnpnpcnph
+1
vote
1
answer
28
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.2k
points)

1k
views
ugcnetdec2014iii
algorithms
pnpnpcnph
+7
votes
2
answers
29
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
(
105k
points)

341
views
cmi2015
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
Linear Algebra Important Points
GATE 2020
OFFICIAL GATE MOCK TEST RELEASED
IIITH: Winter Research Admissions 2019 (For Spring 2020)
TIFR and JEST exam
Follow @csegate
Recent questions tagged pnpnpcnph
Recent Blog Comments
@
[email protected]
Can this be updated?
Even In 2019 my 16 questions goes for negative...
i also don't have any pdf, actually, I added the...
i don't have , if you have upload it
@mohan123 Do you have all standard book...
50,647
questions
56,497
answers
195,490
comments
100,815
users