Recent questions tagged 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

380 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

294 views

admin asked Mar 14, 2023

1 votes

0 answers

3

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

384 views

admin asked Sep 1, 2022

1 votes

0 answers

4

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

382 views

admin asked Sep 1, 2022

0 votes

2 answers

5

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

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

ramraj13

428 views

ramraj13 asked Nov 29, 2021

2 votes

1 answer

6

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

498 views

soujanyareddy13 asked Mar 25, 2021

1 votes

2 answers

7

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

483 views

gatecse asked Dec 9, 2020

1 votes

2 answers

8

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

0 votes

2 answers

9

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

699 views

luc_Bloodstone asked Sep 22, 2019

0 votes

2 answers

10

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

668 views

gatecse asked Sep 13, 2019

1 votes

1 answer

11

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

0 votes

0 answers

12

Proving a problem as NP-complete.
According to this article, A problem X can be proved to be NP-complete if an already existing NP-complete problem (say Y) can be polynomial-time 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 NP-complete? PS: I have already asked this question in cs.stackexchange

According to this article, A problem X can be proved to be NP-complete if an already existing NP-complete problem (say Y) can be polynomial-time reduced to current proble...

commenter commenter

876 views

commenter commenter asked Jun 14, 2019

0 votes

0 answers

13

Is each and every NP complete problem (polynomially) reduced to each and every another NP complete problem?

I know that all NP problems can be reduced to Boolean Satisfiability SAT problem. But my question is whether SAT problem can be reduced to other NP complete problems like...

commenter commenter

362 views

commenter commenter asked Jun 13, 2019

0 votes

0 answers

14

Self-Doubt(P-NP class)
$1)$ If the complement of NP-Complete problem is in NP, then can we also say , for this case complement of NP problem is in NP-Complete ? $2)$ If the complement of NP-Complete problem is in Co-NP, then can we also say, for this case complement of Co-NP problem is in NP-Complete?

$1)$ If the complement of NP-Complete problem is in NP, then can we also say , for this case complement of NP problem is in NP-Complete ?$2)$ If the complement of NP-Comp...

srestha

917 views

srestha asked Apr 22, 2019

1 votes

1 answer

15

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

What will be the answer to this question? L’ is the complement of language L belongs to NP does not always imply thatL’ belongs to NPL’ belongs to P both a and b

Rhythm

1.2k views

Rhythm asked Apr 20, 2019

1 votes

1 answer

16

If there is an $\rm NP$-complete language $L$ whose complement is in $\rm NP$, then...
If there is an $\rm NP$-complete language $L$ whose complement is in $\rm NP$, then the complement of any language in $\rm NP$ is in $\rm NP$ $\rm P$ Both (a) and (b) None of these

If there is an $\rm NP$-complete language $L$ whose complement is in $\rm NP$, then the complement of any language in $\rm NP$ is in$\rm NP$$\rm P$Both (a) and (b)None of...

Rhythm

1.5k views

Rhythm asked Apr 20, 2019

1 votes

1 answer

17

Applied Course | Mock GATE | Test 1 | Question: 20
Assuming $P \neq NP$, Which of the following statements are TRUE? There is no language in $NP$ which has a Deterministic Polynomial time algorithm. There is no language in $P$ which has a Deterministic Polynomial time algorithm. $NP$ is not a subset of $P$ $P$ is not a subset of $NP$

Assuming $P \neq NP$, Which of the following statements are TRUE?There is no language in $NP$ which has a Deterministic Polynomial time algorithm.There is no language in...

Applied Course

509 views

Applied Course asked Jan 16, 2019

0 votes

1 answer

18

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

554 views

admin asked Jan 5, 2019

3 votes

1 answer

19

TIFR CSE 2019 | Part B | Question: 7
A formula is said to be a $3$-CF-formula 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$ ... $\text{3-DF-SAT}$ is NP-complete Neither $\text{3-CF-SAT}$ nor $\text{3-DF-SAT}$ are in P

A formula is said to be a $3$-CF-formula 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 ...

Arjun

1.0k views

Arjun asked Dec 18, 2018

0 votes

1 answer

20

Undirected Graph - Hamiltonian Cycle - NP Complete?
All the places where I have read the Ham-Cycle problem, the graph used is directed. Is the problem of finding Ham-Cycle on an undirected graph also NP-Complete or not?

All the places where I have read the Ham-Cycle problem, the graph used is directed. Is the problem of finding Ham-Cycle on an undirected graph also NP-Complete or not?

gmrishikumar

880 views

gmrishikumar asked Nov 30, 2018

0 votes

0 answers

21

IITD EET

Churchill Khangar

319 views

Churchill Khangar asked Nov 22, 2018

0 votes

0 answers

22

IIT Delhi

Churchill Khangar

478 views

Churchill Khangar asked Nov 22, 2018

0 votes

1 answer

23

TANCET 2016 P Vs NP

Balaji Jegan

198 views

Balaji Jegan asked Oct 23, 2018

0 votes

0 answers

24

self doubt (complexity classes)
why PSpace is more complex to P and NP problem is it same as NP hard problem or NPC problem??can anyone explain it with example.

why PSpace is more complex to P and NP problem is it same as NP hard problem or NPC problem??can anyone explain it with example.

BASANT KUMAR

167 views

BASANT KUMAR asked Sep 1, 2018

1 votes

1 answer

25

REGARDING SYLLABUS
TOPICS LIKE P,NP COMPLETE IS IN SYLLABUS????????

TOPICS LIKE P,NP COMPLETE IS IN SYLLABUS????????

eyeamgj

357 views

eyeamgj asked Aug 3, 2018

0 votes

1 answer

26

self doubt
all NP problems have the complexity exponential ???

all NP problems have the complexity exponential ???

vijju532

227 views

vijju532 asked Jul 2, 2018

0 votes

0 answers

27

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?

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

!KARAN

286 views

!KARAN asked Jun 17, 2018

0 votes

1 answer

28

Np Hard Problems
Are NP-Hard 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 NP-hard but not NPC.Can these also be solved in polynomial time by NTM?

Are NP-Hard 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 cas...

rahul sharma 5

1.2k views

rahul sharma 5 asked Apr 16, 2018

0 votes

1 answer

29

Np-complete Problems
I know that NP-complete problems are the hardest NP problems and every NP problem can be reduced NP-Complete problems in polynomial time. Now, it is said that all NP problems can be solved in Non-deterministic polynomial time, so is it true that ALL NP-COMPLETE PROBLEMS CAN BE SOLVED IN NON-DETERMINISTIC POLYNOMIAL TIME ?

I know that NP-complete problems are the hardest NP problems and every NP problem can be reduced NP-Complete problems in polynomial time. Now, it is said that all NP prob...

Harsh Kumar

760 views

Harsh Kumar asked Mar 20, 2018

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