Recent questions tagged p-np-npc-nph / GATE Overflow for GATE CSE

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

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

273 views

ankit_thawal asked Jan 14, 2018

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

954 views

humblefool asked Jan 6, 2018

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

561 views

hacker16 asked Dec 24, 2017

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

982 views

Arjun asked Dec 10, 2017

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

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

673 views

Bikram asked Aug 12, 2017

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

441 views

Bikram asked Aug 12, 2017

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

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

0 votes

1 answer

41

Virtual Gate Test Series: Algorithms - TSP Problem

firki lama

432 views

firki lama asked Dec 29, 2016

0 votes

0 answers

42

Virtual Gate Test Series: Algorithms - NP Class

firki lama

228 views

firki lama asked Dec 29, 2016

0 votes

1 answer

43

Virtual Gate Test Series: Algorithms - NP Complete Problem

firki lama

459 views

firki lama asked Dec 29, 2016

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

677 views

go_editor asked Dec 29, 2016

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

644 views

go_editor asked Dec 28, 2016

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

405 views

Pankaj Joshi asked Dec 27, 2016

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

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.2k views

go_editor asked Dec 23, 2016

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

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

667 views

Sankaranarayanan P.N asked Oct 27, 2016

0 votes

2 answers

51

Virtual Test series

Jhunjhunuwala

609 views

Jhunjhunuwala asked Sep 25, 2016

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

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

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.6k views

rude asked May 23, 2016

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

770 views

go_editor asked May 19, 2016

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

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

816 views

shreshtha5 asked Dec 3, 2015

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

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

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.8k views

makhdoom ghaya asked Oct 25, 2015

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