search
Log In

Recent questions tagged p-np-npc-nph

0 votes
2 answers
1
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!
asked Sep 22, 2019 in Algorithms luc_Bloodstone 159 views
0 votes
1 answer
2
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 know an ... a polynomial time algorithm for B. We only know an exponential time algorithm for B, but we have a polynomial time algorithm for A.
asked Sep 13, 2019 in Theory of Computation gatecse 79 views
1 vote
0 answers
3
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$
asked Jul 2, 2019 in Algorithms Arjun 180 views
0 votes
0 answers
4
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 need to prove that ... does this reduction have to be only one way to prove a problem is NP-complete? PS: I have already asked this question in cs.stackexchange
asked Jun 14, 2019 in Theory of Computation commenter commenter 159 views
0 votes
0 answers
5
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 travelling salesperson problem TSP, 0/1 knapsack problem. In short are the reductions in NPC problems two ways?
asked Jun 13, 2019 in Theory of Computation commenter commenter 85 views
0 votes
0 answers
6
$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?
asked Apr 22, 2019 in Theory of Computation srestha 128 views
1 vote
1 answer
7
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
asked Apr 20, 2019 in Theory of Computation Rhythm 303 views
1 vote
1 answer
8
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
asked Apr 20, 2019 in Theory of Computation Rhythm 342 views
2 votes
1 answer
9
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$-DF-formula if it is a disjunction (i.e., an OR) of clauses of at most $3$ literals each. Define the ... $\text{3-DF-SAT}$ is NP-complete Neither $\text{3-CF-SAT}$ nor $\text{3-DF-SAT}$ are in P
asked Dec 18, 2018 in Algorithms Arjun 310 views
0 votes
1 answer
10
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?
asked Nov 30, 2018 in Algorithms gmrishikumar 179 views
0 votes
0 answers
11
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?
asked Jun 18, 2018 in Theory of Computation !KARAN 77 views
0 votes
1 answer
12
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?
asked Apr 16, 2018 in Theory of Computation rahul sharma 5 383 views
0 votes
1 answer
13
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 ?
asked Mar 20, 2018 in Theory of Computation Harsh Kumar 314 views
3 votes
1 answer
14
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$ If the best algorithm for $A$ takes ... If we don't know whether there is a polynomial time algorithm for $B$, then there cannot be a polynomial time algorithm for $A$.
asked Feb 5, 2018 in Algorithms Tesla! 555 views
2 votes
0 answers
15
Can Anyone please post the diagram which describes the relation between P, NP, NPSPACE, NP-Hard, EXPONENTIAL TIME etc.
asked Jan 15, 2018 in Algorithms ankit_thawal 87 views
5 votes
0 answers
16
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 still I want someone else to verify it. And please dont say, "it is better to read" because although knowledge is good but time is precious :-)
asked Jan 6, 2018 in Theory of Computation humblefool 299 views
3 votes
1 answer
18
$G$ respresents an undirected graph and a cycle refers to a simple cycle (no repeated edges or vertices). Define the following two languages. $SCYCLE=\{(G,k)\mid G \text{ contains a cycle of length at most k}\}$ ... $SCYCLE \leq_{p} LCYCLE$ (i.e, there is a polynomial time many-to-one reduction from $SCYCLE$ to $LCYCLE$).
asked Dec 10, 2017 in Algorithms Arjun 348 views
1 vote
1 answer
19
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 "turing decidable" 2) http://www. ... ? If they have same expressive power why can't we use DTM in NP decision problems? Thanks for being patient and reading doubt.
asked Nov 29, 2017 in Theory of Computation ♥_Less 313 views
0 votes
2 answers
20
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 can solve and thus we can also ... fact can be verified.hence this Np problem is now P problem Am i correct with these two terms ????????????????
asked Mar 26, 2017 in Algorithms LavTheRawkstar 882 views
3 votes
1 answer
23
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 regular $\mathsf{PRIMES}$ is undecidable $\mathsf{PRIMES}$ is decidable in polynomial time $\mathsf{PRIMES}$ is context free but not regular $\mathsf{PRIMES}$ is NP-complete and P $\neq$ NP
asked Dec 29, 2016 in Others jothee 173 views
2 votes
1 answer
24
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
asked Dec 28, 2016 in Others jothee 131 views
0 votes
0 answers
25
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 the answer is d 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?
asked Dec 28, 2016 in Theory of Computation Pankaj Joshi 94 views
5 votes
1 answer
26
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$ has the binary root $(x_1=1, x_2=0)$. Then ... in polynomial time 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
asked Dec 23, 2016 in Algorithms jothee 386 views
3 votes
1 answer
27
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 if a given $directed$ ... TRUE? Choose 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
asked Dec 23, 2016 in Algorithms jothee 412 views
0 votes
1 answer
28
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??
asked Nov 20, 2016 in Theory of Computation Hradesh patel 193 views
0 votes
1 answer
29
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
asked Oct 27, 2016 in Algorithms Sankaranarayanan P.N 180 views
...