NP - Completeness

In this slide , NP-Completeness is told in a clearer way than most of other staff at the web :
http://courses.cs.washington.edu/courses/cse373/01sp/Lect27_2up.pdf

Examples :
Here are some basic NP -Completeness Questions :
1 - 

Taken from : http://courses.cs.washington.edu/courses/cse373/01sp/sample_final_soln.pdf

2 - The below 6 test questions can be reached from : http://geeksquiz.com/?page_id=681

b.

c.

d.

e.

f.














 What we reviewed above is :
-no NP-Complete problem can be solved in polynomial time. Because, if one NP-Complete problem can be solved in polynomial time, then all NP problems can solved in polynomial time.

-A NP Complete problem has to be in both NP and NP-hard.

-If a NP-complete problem is polynomial-time reducible to R , then R is NP-hard

-If there is no NP-complete problem that is polynomial time Turing-reducible to Q , Then Q can't be NP-hard

-set NP includes both P(Polynomial time solvable) and NP-Complete

-NP-Complete set is intersection of NP and NP-Hard sets.

-all NP problems are decidable in finite set of operations.

-2-SAT is P while 3-SAT is NP Complete

-The problem of determining whether there exists a cycle in an undirected graph is in P , because cycle detection can be done in polynomial time using DFS

-The problem of determining whether there exists a cycle in an undirected graph is in NP,because P is a subset of NP

-If a problem A is NP-Complete, there exists a non-deterministic polynomial time algorithm to solve A. because NP complete is also a subset of NP and NP means Non-deterministic Polynomial time solution exists.

-If we want to prove that a problem X is NP-Hard, we take a known NP-Hard problem Y and reduce Y to X

-The first problem that was proved as NP-complete was the circuit satisfiability problem.

-NP-complete is a subset of NP Hard