Register

GATE IT 2006 | Question: 10

• retagged by
7,266 views
7 7 votes

A problem in NP is NP-complete if

  1. it can be reduced to the 3-SAT problem in polynomial time
  2. the 3-SAT problem can be reduced to it in polynomial time
  3. it can be reduced to any other problem in NP in polynomial time
  4. some problem in NP can be reduced to it in polynomial time

1 Answer

Best answer
12 12 votes

(B) A problem in NP becomes NPC if all NP problems can be reduced to it in polynomial time. This is same as reducing any of the NPC problem to it. 3-SAT being an NPC problem, reducing it to a NP problem would mean that NP problem is NPC.

http://gatecse.in/wiki/NP,_NP_Complete,_NP_Hard

• selected by
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GATE IT 2006 | Quest...Next → · GATE IT 2006 | Quest...
← Previous in category · GATE IT 2007 | Quest...Next in category → · GATE IT 2006 | Quest...
Position:
Show:

Related questions

16 16 votes
7 answers 7 answers
15.2k
15.2k views
Kathleen asked Sep 18, 2014
15,197 views
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}$ respectivelyundecidable and $\text{NP}...
9 9 votes
5 answers 5 answers
9.0k
9.0k views
go_editor asked Sep 28, 2014
8,990 views
GATE CSE 2014 | Set 3 | Question: 19, ISRO2017-78
In the context of modular software design, which one of the following combinations is desirable?High cohesion and high couplingHigh cohesion and low couplingLow cohesion ...
18 18 votes
2 answers 2 answers
9.1k
9.1k views
go_editor asked Feb 12, 2015
9,058 views
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 followi...
37 37 votes
7 answers 7 answers
15.2k
15.2k views
Ishrat Jahan asked Nov 1, 2014
15,234 views
GATE IT 2006 | Question: 65
In the $\text{4B/5B}$ encoding scheme, every $4$ bits of data are encoded in a $5$-bit codeword. It is required that the codewords have at most $1$ leading and at most $1...