The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+6 votes
2.3k views

The problem $3$-SAT and $2$-SAT are 

  1. both in P

  2. both NP complete

  3. NP-complete and in P respectively

  4. undecidable and NP complete respectively

asked in Algorithms by Veteran (69k points)
edited by | 2.3k views

6 Answers

+8 votes
Best answer
answered by Loyal (3.3k points)
selected by
+6 votes

option C

$3$-SAT is NP complete

$2$-SAT is P

answered by Veteran (10.3k points)
edited by
Ans is correct

But sir ,I read that SAT is NP-complete problem so why can't we say that 2-sat is also NP-complete

2-SAT is in P that indicates that there exists  deterministic alg which solves the problem in Polynomial time

so can't we write deterministic alg which solves the problem in Polynomial time  for 3-SAT problem too..

Please explain me this difference sir...
satisfiability problem are not np complete as always . as you see that 2 SAT is not a np complete .

3 SAT problem can be reduced to hamiltonian problem which is a NP complete problem . (with 3 literals )

2 SAT  problem is solved in polynomial time  . ( with 2 literal )

BTW do not call me sir , it sounds strange :D .
+4 votes

Option (c)  NP-complete and in P, respectively is the correct answer.

Reference :http://infolab.stanford.edu/~ullman/ialc/spr10/slides/pnp2.pdf

answered by (235 points)
+2 votes
3 SAT - NPC Problem

2 SAT - p class problem

so option c
answered by Veteran (12.4k points)
–1 vote
3 sat np and 2 sat p problem
answered by (25 points)
–1 vote
Option C is correct.
answered by Loyal (2.8k points)
2 sat is solvable in polynomial time whereas 3 sat is in np
3 Sat in NP-C
Answer:

Related questions



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

33,593 questions
40,128 answers
114,021 comments
38,389 users