Search results for p-np-npc-nph / GATE Overflow for GATE CSE

3 votes

0 answers

1

TIFR CSE 2023 | Part B | Question: 12
A graph $G=(V, E)$ is said to be $k$-colourable if the set $V$ of vertices can be coloured with $k$ colours such that no edge has both its endpoints of the same colour. It is known that the following language $\text{3COL}$ is $\text{NP}$-complete. \[ 3 \ ... $\text{(P1), (P3)}$and $\text{(P4)}$ Only problems $\text{(P1), (P2)}$and $\text{(P4)}$

A graph $G=(V, E)$ is said to be $k$-colourable if the set $V$ of vertices can be coloured with $k$ colours such that no edge has both its endpoints of the same colour. I...

admin

365 views

admin asked Mar 14, 2023

2 votes

0 answers

2

TIFR CSE 2023 | Part B | Question: 14
A $k$-term $T=\ell_{1} \wedge \ell_{2} \wedge \cdots \wedge \ell_{r}$ is defined to be a conjunction of at most $k$ literals, where each literal $\ell_{i}$ is a Boolean variable or its negation and $r \leq k$. A formula $\Phi$ ... $\text{(S1)}$ and $\text{(S3)}$ are true, but $\text{(S2)}$ is not known to be true.

A $k$-term $T=\ell_{1} \wedge \ell_{2} \wedge \cdots \wedge \ell_{r}$ is defined to be a conjunction of at most $k$ literals, where each literal $\ell_{i}$ is a Boolean v...

admin

290 views

admin asked Mar 14, 2023

1 votes

0 answers

3

TIFR CSE 2022 | Part B | Question: 12
Given an undirected graph $G$, an ordering $\sigma$ of its vertices is called a perfect ordering if for every vertex $v$, the neighbours of $v$ which precede $v$ in $\sigma$ form a clique in $G$. Recall that given an undirected ... SPECIAL-COLOURING are in $\mathrm{P}$ Neither of SPECIAL-CLiQUE and SPECIAL-COLOURING is in $\mathrm{P},$ but both are decidable

Given an undirected graph $G$, an ordering $\sigma$ of its vertices is called a perfect ordering if for every vertex $v$, the neighbours of $v$ which precede $v$ in $\sig...

admin

368 views

admin asked Sep 1, 2022

1 votes

0 answers

4

TIFR CSE 2022 | Part B | Question: 10
Consider the assertions $\text{(A1)}$ Given a directed graph $G$ with positive weights on the edges, two special vertices $s$ and $t$, and an integer $k$ - it is $\text{NP}$-complete to determine if $G$ has an $s- t$ path of length at most $k$ ... $\text{A1}$ does not imply $\text{A2}$ and $\text{A2}$ does not imply $\text{A1}$ None of the above.

Consider the assertions$\text{(A1)}$ Given a directed graph $G$ with positive weights on the edges, two special vertices $s$ and $t$, and an integer $k$ - it is $\text{NP...

admin

369 views

admin asked Sep 1, 2022

21 votes

5 answers

5

GATE CSE 2006 | Question: 16, ISRO-DEC2017-27
Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true? R is NP-complete R is NP-hard Q is NP-complete Q is NP-hard

Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Whic...

Rucha Shelke

18.0k views

Rucha Shelke asked Sep 17, 2014

1 votes

2 answers

6

NIELIT Scientific Assistant A 2020 November: 57
Which of the following problem is not $\text{NP}$ complete but undecidable? Partition Problem Halting Problem Hamiltonian Circuit Bin Packing

Which of the following problem is not $\text{NP}$ complete but undecidable?Partition ProblemHalting ProblemHamiltonian CircuitBin Packing

gatecse

466 views

gatecse asked Dec 9, 2020

0 votes

2 answers

7

IIT KGP 2022
Is NP NP hard still in GATE syllabus for 2022 ??

Is NP NP hard still in GATE syllabus for 2022 ??

ramraj13

423 views

ramraj13 asked Nov 29, 2021

10 votes

3 answers

8

GATE IT 2008 | Question: 11
For problems X and Y, Y is NP-complete and X reduces to Y in polynomial time. Which of the following is TRUE? If X can be solved in polynomial time, then so can Y X is NP-complete X is NP-hard X is in NP, but not necessarily NP-complete

For problems X and Y, Y is NP-complete and X reduces to Y in polynomial time. Which of the following is TRUE?If X can be solved in polynomial time, then so can YX is NP-c...

Ishrat Jahan

7.1k views

Ishrat Jahan asked Oct 27, 2014

0 votes

1 answer

9

UPPCL AE 2018:2
Which of the following problems is $\text{NOT NP}$-complete? Checking satisfiability of arbitrary Boolean formulae Checking satisfiability of Boolean formulae in conjunctive normal form $\text{(CNF}$ ... $\text{II}$ only $\text{III}$ only $\text{I}$ only

Which of the following problems is $\text{NOT NP}$-complete?Checking satisfiability of arbitrary Boolean formulaeChecking satisfiability of Boolean formulae in conjunctiv...

admin

546 views

admin asked Jan 5, 2019

2 votes

1 answer

10

TIFR CSE 2021 | Part B | Question: 4
Consider the following two languages. ... $\text{NP}$ vs. $\text{P}$ question.

Consider the following two languages.$\begin{array}{rcl} \text{PRIME} & = & \{ 1^{n} \mid n \text{ is a prime number} \}, \\ \text{FACTOR} & = & \{ 1^{n}0 1^{a} 01^{b} ...

soujanyareddy13

489 views

soujanyareddy13 asked Mar 25, 2021

19 votes

2 answers

11

GATE CSE 2008 | Question: 44
The subset-sum problem is defined as follows: Given a set $S$ of $n$ positive integers and a positive integer $W$, determine whether there is a subset of $S$ whose elements sum to $W$. An algorithm $Q$ solves this problem in $O(nW)$ time. ... input is encoded in binary The subset sum problem belongs to the class $\text{NP}$ The subset sum problem is $\text{NP-hard}$

The subset-sum problem is defined as follows: Given a set $S$ of $n$ positive integers and a positive integer $W$, determine whether there is a subset of $S$ whose elemen...

Kathleen

13.3k views

Kathleen asked Sep 12, 2014

3 votes

2 answers

12

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

0 votes

2 answers

13

CMI2019-A-8
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.

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 b...

gatecse

661 views

gatecse asked Sep 13, 2019

1 votes

2 answers

14

NIELIT 2016 MAR Scientist B - Section C: 19
If there is in NP-Complete language L whose complement is in NP, then complement of any language in NP is in P NP both (A) and (B) None of these

If there is in NP-Complete language L whose complement is in NP, then complement of any language in NP is inPNPboth (A) and (B)None of these

admin

1.7k views

admin asked Mar 31, 2020

1 votes

1 answer

15

UGC NET CSE | June 2019 | Part 2 | Question: 67
Consider the complexity class $CO-NP$ as the set of languages $L$ such that $\overline{L} \in NP$, and the following two statements: $S_1: \: P \subseteq CO-NP$ $S_2: \: \text{ If } NP \neq CO-NP, \text{ then } P \neq NP$ Which of the following is/are correct? Only $S_1$ Only $S_2$ Both $S_1$ and $S_2$ Neither $S_1$ nor $S_2$

Consider the complexity class $CO-NP$ as the set of languages $L$ such that $\overline{L} \in NP$, and the following two statements:$S_1: \: P \subseteq CO-NP$$S_2: \: \t...

Arjun

1.2k views

Arjun asked Jul 2, 2019

7 votes

3 answers

16

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

9 votes

3 answers

17

GATE CSE 1992 | Question: 02,vi
Which of the following problems is not $\text{NP}$-hard? Hamiltonian circuit problem The $0/1$ Knapsack problem Finding bi-connected components of a graph The graph coloring problem

Which of the following problems is not $\text{NP}$-hard?Hamiltonian circuit problemThe $0/1$ Knapsack problemFinding bi-connected components of a graphThe graph coloring ...

Kathleen

7.4k views

Kathleen asked Sep 12, 2014

15 votes

7 answers

18

GATE CSE 2004 | Question: 30, ISRO2017-10
The problem $\text{3-SAT}$ and $\text{2-SAT}$ are both in $\text{P}$ both $\text{NP}$ complete $\text{NP}$-complete and in $\text{P}$ respectively undecidable and $\text{NP}$ complete respectively

The problem $\text{3-SAT}$ and $\text{2-SAT}$ are both in $\text{P}$both $\text{NP}$ complete$\text{NP}$-complete and in $\text{P}$ respectivelyundecidable and $\text{NP}...

Kathleen

11.8k views

Kathleen asked Sep 18, 2014

16 votes

2 answers

19

GATE CSE 2015 Set 2 | Question: 2
Consider two decision problems $Q_1, Q_2$ such that $Q_1$ reduces in polynomial time to 3-SAT and 3-SAT reduces in polynomial time to $Q_2$. Then which one of the following is consistent with the above statement? $Q_1$ is in NP, $Q_2$ is NP hard. $Q_2$ is in NP, $Q_1$ is NP hard. Both $Q_1$ and $Q_2$ are in NP. Both $Q_1$ and $Q_2$ are in NP hard.

Consider two decision problems $Q_1, Q_2$ such that $Q_1$ reduces in polynomial time to 3-SAT and 3-SAT reduces in polynomial time to $Q_2$. Then which one of the followi...

go_editor

6.5k views

go_editor asked Feb 12, 2015

0 votes

2 answers

20

Understanding Np-hard
I am having difficulty in understanding np and np-hard 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!

I am having difficulty in understanding np and np-hard topic in algorithms. If someone can provide some good source to learn about it in easy manner it would be a real he...

luc_Bloodstone

695 views

luc_Bloodstone asked Sep 22, 2019

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