Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Filter
Profile
Wall
Recent activity
All questions
All answers
Exams Taken
All Blogs
Recent activity by happysingh
2
answers
1
#Algorithms Time Complexity Analysis of Multistage Graph using Bottom Up Dynamic Programming
Time complexity of Multistage Graph is O(n2) or O(V2) but then some people says it's O(E). So, from O(V2) to O(E) are they taking about dense/complete graphs in which number of edges |E| = |V2|? Kindly help!
Time complexity of Multistage Graph is O(n2) or O(V2) but then some people says it's O(E). So, from O(V2) to O(E) are they taking about dense/complete graphs in which num...
5.1k
views
answered
Apr 26, 2020
Algorithms
algorithms
dynamic-programming
+
–
1
answer
2
GATE CSE 2009 | Question: 14
Let $\pi_A$ be a problem that belongs to the class NP. Then which one of the following is TRUE? There is no polynomial time algorithm for $\pi_A$. If $\pi_A$ can be solved deterministically in polynomial time, then P = NP. If $\pi_A$ is NP-hard, then it is NP-complete. $\pi_A$ may be undecidable.
Let $\pi_A$ be a problem that belongs to the class NP. Then which one of the following is TRUE?There is no polynomial time algorithm for $\pi_A$.If $\pi_A$ can be solved ...
9.4k
views
commented
Apr 20, 2020
Theory of Computation
gatecse-2009
theory-of-computation
p-np-npc-nph
+
–
2
answers
3
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...
6.5k
views
commented
Apr 20, 2020
Theory of Computation
gatecse-2015-set2
algorithms
p-np-npc-nph
easy
out-of-syllabus-now
+
–
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register