Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged p-np-npc-nph
3
votes
2
answers
31
CMI2017-A-10
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$.
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 exponenti...
Tesla!
2.3k
views
Tesla!
asked
Feb 4, 2018
Algorithms
cmi2017
algorithms
reduction
p-np-npc-nph
+
–
2
votes
0
answers
32
Self Doubt IMP
Can Anyone please post the diagram which describes the relation between P, NP, NPSPACE, NP-Hard, EXPONENTIAL TIME etc.
Can Anyone please post the diagram which describes the relation between P, NP, NPSPACE, NP-Hard, EXPONENTIAL TIME etc.
ankit_thawal
277
views
ankit_thawal
asked
Jan 14, 2018
Algorithms
p-np-npc-nph
+
–
5
votes
0
answers
33
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/gate-cse-2016-syllabus/ , 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 :-)
I know this questions is already asked but no answers are yet givenIS P NP STILL PRESENT IN GATE 2018 SYLLABUS? The Official Syllabus EXCLUDES those topics and according ...
humblefool
960
views
humblefool
asked
Jan 6, 2018
Theory of Computation
p-np-npc-nph
theory-of-computation
syllabus
+
–
0
votes
0
answers
34
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}
did P and NP is still in the syllabus? @ COMPUTABILITY AND COMPLEXITY{TOC}
hacker16
564
views
hacker16
asked
Dec 24, 2017
Theory of Computation
syllabus
p-np-npc-nph
theory-of-computation
+
–
4
votes
1
answer
35
TIFR CSE 2018 | Part B | Question: 15
$G$ respresents an undirected graph and a cycle refers to a simple cycle (no repeated edges or vertices). Define the following two languages. $\text{SCYCLE}=\{(G,k)\mid G \text{ contains a cycle of length at most k}\}$ ... $\text{SCYCLE}$ to $\text{LCYCLE}$).
$G$ respresents an undirected graph and a cycle refers to a simple cycle (no repeated edges or vertices). Define the following two languages.$\text{SCYCLE}=\{(G,k)\mid G ...
Arjun
990
views
Arjun
asked
Dec 10, 2017
Theory of Computation
tifr2018
theory-of-computation
reduction
p-np-npc-nph
non-gate
+
–
1
votes
1
answer
36
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.
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 unde...
♥_Less
1.1k
views
♥_Less
asked
Nov 29, 2017
Theory of Computation
theory-of-computation
turing-machine
decidability
self-doubt
p-np-npc-nph
+
–
0
votes
1
answer
37
Test by Bikram | Theory of Computation | Test 2 | Question: 21
A problem $X$ is reducible to problem $Y$ in polynomial time. All the problems in NP can also be reduced to problem $X$. Then, which of the following statements are true? S1 : $X$ is NP complete and $Y$ is in NP. S2 : $X$ is NP complete and ... hard. S4 : $X$ and $Y$ are NP hard. S4 only S1, S2 & S3 S3 & S4 S1, S2, S3 & S4
A problem $X$ is reducible to problem $Y$ in polynomial time. All the problems in NP can also be reduced to problem $X$. Then, which of the following statements are true?...
Bikram
691
views
Bikram
asked
Aug 12, 2017
Theory of Computation
tbb-toc-2
p-np-npc-nph
theory-of-computation
reduction
+
–
0
votes
1
answer
38
Test by Bikram | Theory of Computation | Test 2 | Question: 4
Which of the following statements is FALSE? Recursive Enumerable Languages are not closed under set difference and complementation. Complement of context-free language must be recursive. If a problem $X$ is NP complete and $X \in P,$ then $NP = P$. Membership problem is not decidable for Recursive Languages.
Which of the following statements is FALSE?Recursive Enumerable Languages are not closed under set difference and complementation.Complement of context-free language must...
Bikram
453
views
Bikram
asked
Aug 12, 2017
Theory of Computation
tbb-toc-2
theory-of-computation
closure-property
p-np-npc-nph
+
–
1
votes
2
answers
39
P and NP
P and NP concepts are there in gate syllabus?????????????????????????????????????????????
P and NP concepts are there in gate syllabus?????????????????????????????????????????????
akankshadewangan24
2.0k
views
akankshadewangan24
asked
Jun 20, 2017
Algorithms
algorithms
p-np-npc-nph
+
–
0
votes
2
answers
40
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 ????????????????
what i have tried to get out the conslusion for P problem is that P problemThese are set of those yes/no problems which can solved using polynomic time complexity algroi...
LavTheRawkstar
2.3k
views
LavTheRawkstar
asked
Mar 26, 2017
Algorithms
p-np-npc-nph
+
–
0
votes
1
answer
41
Virtual Gate Test Series: Algorithms - TSP Problem
firki lama
432
views
firki lama
asked
Dec 29, 2016
Algorithms
algorithms
p-np-npc-nph
virtual-gate-test-series
+
–
0
votes
0
answers
42
Virtual Gate Test Series: Algorithms - NP Class
firki lama
229
views
firki lama
asked
Dec 29, 2016
Algorithms
algorithms
p-np-npc-nph
virtual-gate-test-series
+
–
0
votes
1
answer
43
Virtual Gate Test Series: Algorithms - NP Complete Problem
firki lama
461
views
firki lama
asked
Dec 29, 2016
Algorithms
algorithms
p-np-npc-nph
virtual-gate-test-series
+
–
5
votes
1
answer
44
TIFR CSE 2016 | Part B | Question: 8
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 decidable in polynomial time $\mathsf{PRIMES}$ is context free but not regular $\mathsf{PRIMES}$ is NP-complete and P $\neq$ NP
Consider the following language$$\mathsf{PRIMES} = \Biggl\{ \underbrace{111 \dots 11}_{p \: \text{ times} } : \: p \: \text{ is prime } \Biggl\}$$Then, which of the follo...
go_editor
679
views
go_editor
asked
Dec 29, 2016
Theory of Computation
tifr2016
theory-of-computation
decidability
p-np-npc-nph
+
–
3
votes
1
answer
45
TIFR CSE 2016 | Part B | Question: 3
Assume $P \neq NP$. Which of the following is not TRUE? $2$-SAT in NP $2$-SAT in coNP $3$-SAT is polynmial-time reducible to $2$-SAT 4-SAT is polynmial-time reducible to $3$-SAT $2$-SAT in P
Assume $P \neq NP$. Which of the following is not TRUE?$2$-SAT in NP$2$-SAT in coNP$3$-SAT is polynmial-time reducible to $2$-SAT4-SAT is polynmial-time reducible to $3$-...
go_editor
649
views
go_editor
asked
Dec 28, 2016
Theory of Computation
tifr2016
theory-of-computation
reduction
p-np-npc-nph
+
–
0
votes
0
answers
46
MadeEasy Subject Test: Theory of Computation - P Np Npc Nph
Let L1 = Φ and L2 = Σ*. Then which of the following is correct? L1 is NP-complete, L2 is not NP-complete L1 is not NP-complete, L2 is NP-complete Both L1 and L2 are NP-complete Neither L1 nor L2 is NP-complete 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?
Let L1 = Φ and L2 = Σ*. Then which of the following is correct?L1 is NP-complete, L2 is not NP-completeL1 is not NP-complete, L2 is NP-completeBoth L1 and L2 are NP-com...
Pankaj Joshi
413
views
Pankaj Joshi
asked
Dec 27, 2016
Theory of Computation
made-easy-test-series
theory-of-computation
p-np-npc-nph
+
–
5
votes
1
answer
47
TIFR CSE 2017 | Part B | Question: 15
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$ ... is NP-hard, but not in NP is in NP, but not in P and not NP-hard is both in NP and NP-hard
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 eva...
go_editor
1.1k
views
go_editor
asked
Dec 23, 2016
Algorithms
tifr2017
algorithms
p-np-npc-nph
+
–
4
votes
1
answer
48
TIFR CSE 2017 | Part B | Question: 2
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 ... 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
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{N...
go_editor
1.3k
views
go_editor
asked
Dec 23, 2016
Algorithms
tifr2017
algorithms
graph-algorithms
p-np-npc-nph
+
–
0
votes
1
answer
49
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 (2-SAT) somy answer is 1 but answer given 2 here also eulerian path ?? how to appraoch these type of question Plz explain??
Q. consider the following problem:a) Eulerian pathb) 2- SATc) Constraint reachibiltyd)graph coloringnumber of problem which is polynomial solvable?? i am get only b (2-SA...
Hradesh patel
427
views
Hradesh patel
asked
Nov 20, 2016
Theory of Computation
made-easy-test-series
algorithms
p-np-npc-nph
+
–
0
votes
1
answer
50
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 3-SAT 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
A problem in NP is NP complete ifA) Some problem in NP can be reduced to it in polynomial timeB) The 3-SAT problem can be reduced to it in polynomial timeC) It can be red...
Sankaranarayanan P.N
669
views
Sankaranarayanan P.N
asked
Oct 27, 2016
Algorithms
p-np-npc-nph
+
–
0
votes
2
answers
51
Virtual Test series
Jhunjhunuwala
619
views
Jhunjhunuwala
asked
Sep 25, 2016
Algorithms
test-series
time-complexity
p-np-npc-nph
virtual-gate-test-series
+
–
1
votes
1
answer
52
UGC NET CSE | December 2014 | Part 3 | Question: 33
We can show that the clique problem is $NP$-hard by proving that CLIQUE $\leq$ P 3-CNF_SAT CLIQUE $\leq$ P VERTEX_COVER CLIQUE $\leq$ P SUBSET_SUM None of the above
We can show that the clique problem is $NP$-hard by proving thatCLIQUE $\leq$ P 3-CNF_SATCLIQUE $\leq$ P VERTEX_COVERCLIQUE $\leq$ P SUBSET_SUMNone of the above
makhdoom ghaya
3.6k
views
makhdoom ghaya
asked
Jul 28, 2016
Algorithms
ugcnetcse-dec2014-paper3
algorithms
p-np-npc-nph
+
–
7
votes
3
answers
53
CMI2015-A-06
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$.
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$ ...
go_editor
2.1k
views
go_editor
asked
May 27, 2016
Algorithms
cmi2015
algorithms
p-np-npc-nph
+
–
1
votes
1
answer
54
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.
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 reduc...
rude
2.7k
views
rude
asked
May 23, 2016
Algorithms
time-complexity
dynamic-programming
p-np-npc-nph
+
–
2
votes
1
answer
55
CMI2010-A-10
Consider the following statements. NP-complete problems are those that we know we can never solve efficiently. If we find an efficient algorithm for one NP-complete problem, then we can solve all NP-complete problems efficiently. Checking whether a number is a prime is an NP-complete ... are false but $2$ is true. $2$ and $3$ are true but $1$ is false. All three statements are false.
Consider the following statements.NP-complete problems are those that we know we can never solve efficiently.If we find an efficient algorithm for one NP-complete problem...
go_editor
773
views
go_editor
asked
May 19, 2016
Algorithms
cmi2010
algorithms
p-np-npc-nph
+
–
5
votes
2
answers
56
TIFR CSE 2015 | Part B | Question: 13
Two undirected graphs $G_{1}=(V_{1}, E_{1})$ and $G_{2}= (V_{2}, E_{2})$ are said to be isomorphic if there exist a bijection $\pi: V_{1} \rightarrow V_{2}$ such that for all $u, v \in V_{1}, (u, v) \in E_{1}$ ... $L$ is $NP$- hard. $L$ is undecidable. Only $(i)$ Only $(ii)$ Only $(iii)$ $(i)$ and $(ii)$ $(ii)$ and $(iii)$
Two undirected graphs $G_{1}=(V_{1}, E_{1})$ and $G_{2}= (V_{2}, E_{2})$ are said to be isomorphic if there exist a bijection $\pi: V_{1} \rightarrow V_{2}$ such that for...
makhdoom ghaya
1.0k
views
makhdoom ghaya
asked
Dec 8, 2015
Algorithms
tifr2015
graph-theory
graph-isomorphism
p-np-npc-nph
non-gate
+
–
1
votes
1
answer
57
NP complete
Q). Which of the following can we infer from the fact that the travelling salesperson problem is $NP$-complete.if we assume that $P$ is not equal to $NP$ ? A). There does not exist an algorithm that solves arbitrary instances of $TSP$ problem. B). ... algorithm that efficiently solves arbitrary instances of the $TSP$ problem , but no one has been able to find it. D). None of these
Q). Which of the following can we infer from the fact that the travelling salesperson problem is $NP$-complete.if we assume that $P$ is not equal to $NP$ ?A). There does ...
shreshtha5
818
views
shreshtha5
asked
Dec 3, 2015
Algorithms
p-np-npc-nph
+
–
7
votes
1
answer
58
TIFR CSE 2012 | Part B | Question: 20
This question concerns the classes $P$ and $NP.$ If you are familiar with them, you may skip the definitions and go directly to the question. Let $L$ be a set. We say that $L$ is in $P$ if there is some algorithm which given input $x$ decides if ... $\text{MATCH} \notin P\text{ and } \overline{\text{MATCH}} \notin P$ none of the above
This question concerns the classes $P$ and $NP.$ If you are familiar with them, you may skip the definitions and go directly to the question.Let $L$ be a set. We say that...
Arjun
1.0k
views
Arjun
asked
Nov 14, 2015
Graph Theory
tifr2012
graph-theory
graph-matching
p-np-npc-nph
+
–
4
votes
1
answer
59
TIFR CSE 2013 | Part B | Question: 7
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.
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 polyno...
makhdoom ghaya
1.7k
views
makhdoom ghaya
asked
Nov 6, 2015
Algorithms
tifr2013
algorithms
p-np-npc-nph
+
–
7
votes
1
answer
60
TIFR CSE 2011 | Part B | Question: 37
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 ... in polynomial time, however the forward problem is $NP$-hard. Both the forward and reverse problem are $NP$-hard. None of the above.
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 proble...
makhdoom ghaya
1.9k
views
makhdoom ghaya
asked
Oct 25, 2015
Algorithms
tifr2011
algorithms
p-np-npc-nph
+
–
Page:
« prev
1
2
3
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register