Login
Register
@
Dark Mode
Profile
Edit my Profile
Messages
My favorites
Register
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Years
Blogs
New Blog
Exams
Dark Mode
Recent questions tagged p-np-npc-nph
1
vote
0
answers
1
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.
admin
asked
in
Algorithms
Sep 1
by
admin
36
views
tifr2022
algorithms
graph-connectivity
p-np-npc-nph
1
vote
0
answers
2
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
admin
asked
in
Graph Theory
Sep 1
by
admin
61
views
tifr2022
graph-theory
graph-coloring
p-np-npc-nph
0
votes
2
answers
3
IIT KGP 2022
Is NP NP hard still in GATE syllabus for 2022 ??
ramraj13
asked
in
Algorithms
Nov 29, 2021
by
ramraj13
179
views
p-np-npc-nph
syllabus
1
vote
1
answer
4
TIFR CSE 2021 | Part B | Question: 4
Consider the following two languages. ... $\text{NP}$ vs. $\text{P}$ question.
soujanyareddy13
asked
in
Theory of Computation
Mar 25, 2021
by
soujanyareddy13
259
views
tifr2021
theory-of-computation
p-np-npc-nph
1
vote
2
answers
5
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
gatecse
asked
in
Theory of Computation
Dec 9, 2020
by
gatecse
154
views
nielit-sta-2020
theory-of-computation
p-np-npc-nph
1
vote
2
answers
6
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
Lakshman Patel RJIT
asked
in
Theory of Computation
Mar 31, 2020
by
Lakshman Patel RJIT
1.1k
views
nielit2016mar-scientistb
theory-of-computation
p-np-npc-nph
0
votes
2
answers
7
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!
luc_Bloodstone
asked
in
Algorithms
Sep 22, 2019
by
luc_Bloodstone
498
views
p-np-npc-nph
algorithms
0
votes
2
answers
8
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.
gatecse
asked
in
Theory of Computation
Sep 13, 2019
by
gatecse
311
views
cmi2019
reduction
p-np-npc-nph
1
vote
1
answer
9
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$
Arjun
asked
in
Algorithms
Jul 2, 2019
by
Arjun
832
views
ugcnetcse-june2019-paper2
p-np-npc-nph
0
votes
0
answers
10
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
commenter commenter
asked
in
Theory of Computation
Jun 14, 2019
by
commenter commenter
510
views
p-np-npc-nph
theory-of-computation
0
votes
0
answers
11
Is each and every NP complete problem (polynomially) reduced to each and every another NP complete problem?
commenter commenter
asked
in
Theory of Computation
Jun 13, 2019
by
commenter commenter
245
views
p-np-npc-nph
theory-of-computation
time-complexity
0
votes
0
answers
12
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?
srestha
asked
in
Theory of Computation
Apr 22, 2019
by
srestha
462
views
p-np-npc-nph
theory-of-computation
1
vote
1
answer
13
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
Rhythm
asked
in
Theory of Computation
Apr 20, 2019
by
Rhythm
698
views
p-np-npc-nph
1
vote
1
answer
14
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
Rhythm
asked
in
Theory of Computation
Apr 20, 2019
by
Rhythm
1.0k
views
theory-of-computation
time-complexity
p-np-npc-nph
1
vote
1
answer
15
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$
Applied Course
asked
in
Algorithms
Jan 16, 2019
by
Applied Course
306
views
applied-course-2019-mock1
algorithms
p-np-npc-nph
0
votes
1
answer
16
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
Lakshman Patel RJIT
asked
in
Digital Logic
Jan 5, 2019
by
Lakshman Patel RJIT
194
views
uppcl2018
digital-logic
boolean-algebra
p-np-npc-nph
3
votes
1
answer
17
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
Arjun
asked
in
Theory of Computation
Dec 18, 2018
by
Arjun
769
views
tifr2019
theory-of-computation
p-np-npc-nph
0
votes
1
answer
18
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?
gmrishikumar
asked
in
Graph Theory
Nov 30, 2018
by
gmrishikumar
510
views
graph-theory
hamiltonian-cycle
p-np-npc-nph
0
votes
0
answers
19
IITD EET
Churchill Khangar
asked
in
Algorithms
Nov 22, 2018
by
Churchill Khangar
167
views
graph-algorithms
p-np-npc-nph
0
votes
0
answers
20
IIT Delhi
Churchill Khangar
asked
in
Algorithms
Nov 22, 2018
by
Churchill Khangar
345
views
algorithms
p-np-npc-nph
0
votes
1
answer
21
TANCET 2016 P Vs NP
Balaji Jegan
asked
in
Algorithms
Oct 23, 2018
by
Balaji Jegan
98
views
tancet
p-np-npc-nph
0
votes
0
answers
22
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.
BASANT KUMAR
asked
in
Algorithms
Sep 1, 2018
by
BASANT KUMAR
104
views
p-np-npc-nph
1
vote
1
answer
23
REGARDING SYLLABUS
TOPICS LIKE P,NP COMPLETE IS IN SYLLABUS????????
eyeamgj
asked
in
Algorithms
Aug 3, 2018
by
eyeamgj
128
views
syllabus
p-np-npc-nph
0
votes
1
answer
24
self doubt
all NP problems have the complexity exponential ???
vijju532
asked
in
Algorithms
Jul 2, 2018
by
vijju532
120
views
algorithms
p-np-npc-nph
time-complexity
0
votes
0
answers
25
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?
!KARAN
asked
in
Theory of Computation
Jun 18, 2018
by
!KARAN
201
views
theory-of-computation
p-np-npc-nph
decidability
0
votes
1
answer
26
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?
rahul sharma 5
asked
in
Theory of Computation
Apr 16, 2018
by
rahul sharma 5
757
views
p-np-npc-nph
theory-of-computation
0
votes
1
answer
27
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 ?
Harsh Kumar
asked
in
Theory of Computation
Mar 20, 2018
by
Harsh Kumar
588
views
p-np-npc-nph
theory-of-computation
3
votes
2
answers
28
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$.
Tesla!
asked
in
Algorithms
Feb 5, 2018
by
Tesla!
1.9k
views
cmi2017
algorithms
reduction
p-np-npc-nph
2
votes
0
answers
29
Self Doubt IMP
Can Anyone please post the diagram which describes the relation between P, NP, NPSPACE, NP-Hard, EXPONENTIAL TIME etc.
ankit_thawal
asked
in
Algorithms
Jan 15, 2018
by
ankit_thawal
183
views
p-np-npc-nph
5
votes
0
answers
30
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 :-)
humblefool
asked
in
Theory of Computation
Jan 6, 2018
by
humblefool
674
views
p-np-npc-nph
theory-of-computation
syllabus
Page:
1
2
3
next »
Subscribe to GATE CSE 2023 Test Series
Subscribe to GO Classes for GATE CSE 2023
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
POWER GRID CORPORATION OF INDIA LIMITED
INSTITUTE OF BANKING PERSONNEL SELECTION
GATE Overflow books for TIFR, ISRO, UGCNET and NIELIT
RECRUITMENT IN OIL AND GAS CORPORATION LIMITED
Aptitude Overflow Book
Subjects
All categories
General Aptitude
(2.4k)
Engineering Mathematics
(9.1k)
Digital Logic
(3.2k)
Programming and DS
(5.8k)
Algorithms
(4.5k)
Theory of Computation
(6.6k)
Compiler Design
(2.3k)
Operating System
(4.9k)
Databases
(4.5k)
CO and Architecture
(3.7k)
Computer Networks
(4.5k)
Non GATE
(1.3k)
Others
(2.4k)
Admissions
(647)
Exam Queries
(841)
Tier 1 Placement Questions
(17)
Job Queries
(74)
Projects
(9)
Unknown Category
(855)
Recent questions tagged p-np-npc-nph
Recent Blog Comments
@abir_banerjee Thanks Abir. I'm third year...
@nolan_keats Currently I am in third year...
@abir_banerjee thank you Abir.Supposing you...
@nolan_keats just a suggestion as I also...
@abir_banerjee Hope I can do this in span of one...