Arjun Suresh at 13:36, 30 July 2015

2015-07-30T13:36:17Z

Starry Starr at 00:52, 7 May 2015

2015-05-07T00:52:58Z

Starry Starr: Created page with "Category:GATE Subjects in CSE"

2015-05-07T00:31:51Z

Created page with "Category:GATE Subjects in CSE"

New page

[[Category:GATE Subjects in CSE]]

← Older revision		Revision as of 13:36, 30 July 2015
Line 1:		Line 1:
		+	[http://www.gatecse.org/theory-of-computation/ Webpage for Theory of Computation]
		+
	<!--		<!--
	http://gatenotes.wordpress.com/theory-of-computing/-->		http://gatenotes.wordpress.com/theory-of-computing/-->

← Older revision		Revision as of 00:52, 7 May 2015
Line 1:		Line 1:
		+	<!--
		+	http://gatenotes.wordpress.com/theory-of-computing/-->
		+
		+	[http://www.youtube.com/playlist?list=PL601FC994BDD963E4 Video lectures by Shai Simonson] are the best
		+
		+	Here is the first video from the series
		+
		+	{{#ev:youtube\|HyUK5RAJg1c}}
		+
		+
		+	Here are few terms which you must be familiar with
		+
		+	[http://www.ecst.csuchico.edu/~amk/foo/csci356/notes/ch11/NP2.html NP Complete]
		+
		+	[http://csfundas.wordpress.com/theory-of-computation-2/recursively-enumerable/ Recursively Enumerable Sets]
		+
		+	This post describes about Computability concepts like SAT / NP completeness
		+
		+	P represents the class of problems that can be solved in polynomial time
		+
		+	NP represents the class of problems whose solutions can be verified in polynomial time
		+
		+	In other words, nondeterministically guess the solution and verify it in polynomial time. The guessing is nondeterministic and verification is polynomial. Thus nondeterministic polynomial (NP) time
		+
		+	If P were equal to NP, there would be amazing consequences. It means every problem verifiable in polynomial time could also be solved in polynomial time, all combinatorial optimizations could be solved in polynomial time. The curse of combinatorial explosions would be gone. Seems unlikely to be true… however NO counterproof (namely P!=NP) has been found.
		+
		+	===SAT problem (introduced by scientist Cook)===
		+
		+	The most important achievement of Cook is to show that P=NP iff a particular computational problem called SAT is in P.
		+
		+	Cook showed that any problem in NP can be transformed to a corresponding instance of SAT problem in such a way that the original has a solution iff the satisfiability instance has. Moreover, this translation can be done in polynomial time. In other words SAT problem is general enough to capture the structure of any problem in NP. It follows that if we can solve the SAT problem in polynomial time, then we would be able to construct a polynomial time algorithm to solve any problem in NP.
		+
		+	The SAT problem is one archetypal problem. In the field of combinatorial optimization , there is one archetypal problem (integer linear programming) and many combinatorial problems can be stated in terms of ILP.
		+
		+	===NP Completeness (introduced by Prof. Karp)===
		+
		+	Karp decided to investigate whether certain classic combinatorial problems long believed to be intractable were also archetypal in Cook’s sense. Karp called them “polynomial complete” (later known as NP complete)
		+
		+	A problem is said to be NP complete if it lies in the class NP and every problem in NP is polynomially reducible to it. Thus by Cook’s theorem the SAT problem is NP complete. To show a given problem in NP is NP complete it if sufficient to show that some problem already known to be NP complete is polynomial time reducible to it. By constructing a series of polynomial reductions, Karp showed that most problems were NP complete.
		+
		+	<!--[{{fullurl:{{FULLPAGENAMEE}}\|action=pdfbook&format=html}} download this selection of articles as a PDF book]-->
		+
		+	[[Category:GATE Subjects in CSE]]
		+
		+
		+
	[[Category:GATE Subjects in CSE]]		[[Category:GATE Subjects in CSE]]

Category:Theory of Computation - Revision history

Arjun Suresh at 13:36, 30 July 2015

Starry Starr at 00:52, 7 May 2015

Starry Starr: Created page with "Category:GATE Subjects in CSE"