New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Theory of Computation

by: Mrs. Carolyne Abbott

Theory of Computation CS 3102

Mrs. Carolyne Abbott
GPA 3.71

David Evans

Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

David Evans
Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 4 page Class Notes was uploaded by Mrs. Carolyne Abbott on Monday September 21, 2015. The Class Notes belongs to CS 3102 at University of Virginia taught by David Evans in Fall. Since its upload, it has received 43 views. For similar materials see /class/209649/cs-3102-university-of-virginia in ComputerScienence at University of Virginia.


Reviews for Theory of Computation


Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/21/15
NP Cornpleteness Lecture for CS 302 l Non deterministic polynomial time I Deterministic Polynomial Time The TM takes at most OnG steps to accept a string of length n I Nondeterministic Polynomial Time The TM takes at most Onc steps on each computation path to accept a string of length n P vs NP I Are nondeterministic Turing machines really more powerful efficient than deterministic ones I Essence of P vs NP problem l Traveling Salesperson Problem I You have to visit If cities I You want to make the shortest trip I How could you do this I What if you had a machine that could guess l The Class P and the Class NP I P L L is accepted by a deterministic Turing Machine in polynomial time I NP L L is accepted by a non deterministic Turing Machine in polynomial time I They are sets of languages Does Non Dete rminism matte r Firms Auwma av Push Down Automate Nol Yesl DFANFA DFA not NFA PNPP I No one knows it this is true I How can we make progress on this problem Progress I P NP it every NP problem has a deterministic polynomial algorithm I We could find an algorithm for every NP problem I Seems hard I We could use polynomial time reductions to find the hardest problems and just work on those Reductions I Real world examples a Finding your way around the city reduces to reading a map a Traveling from Richmond to Cville reduces to driving a car in Other suggestions i Polynomial tilne reductions I PARTITION nn2 nk we can split the integers into two sets which sum to halt I SUBSETSUM ltnn2 nKmgt there exists a subset which sums to m I 1 It I can solve SUBSETSUM how can I use that to solve an instance of PARTITION I 2 It I can solve PARTITION how can I use that to solve an instance of SUBSETSUM i Polynomial Reductions I 1 Partition REDUCES to SubsetSum I 2 SubsetSum REDUCES to Partition I Therefore they are equivalently hard in Partition ltp SubsetSum u SubsetSum ltp Partition I How long does the reduction take I How could you take advantage of an exponential time reduction NP Completeness I How would you define NPComplete I They are the hardest problems in NP i De nition ofNP Complete I Q is an NPComplete problem it I 1 Q is in NP I 2 every other NP problem polynomial time reducible to Q i Getting Started I How do you show that EVERY NP problem reduces to Q I One way would be to already have an NP Complete problem and just reduce from that kt My e at ry P3 NPrCornpleie 4 em Ptv Probl i Reminder Undecidability I How do you show a language is undecidable I One way would be to already have an undecidable problem and just reduce from that Li L2 Hailing La Problem 439 O H i SAT I SAT t t is a Boolean Formula with a satisfying assignment nquot 11 V m V 12 va V 112 V 13952 I Is SAT in NP I Cook Levin Theorem 1971 I SAT is NPComplete ly u want to see the prooI It is Theorem 7 37 m Sipser assigned readingl oryou can take heory on are not responsible lor Knowing the proof NP Complete I To prove a problem is NPComplete show a polynomial time reduction from 3SAT I Other NPComplete Problems 1 PARTITION a SUBSETSUM u CLIQUE u HAMILTONIAN PATH TSP u GRAPH COLORING u MINESWEEPER and many more I 3 SAT I 3SAT fl is in Conjunctive Normal Form each clause has exactly 3 literals and is satistiable I 3SAT is NPComplete 2SAT is in P I NP Completeness Proof Method I To show that Q is NPComplete I 1 Show that Q is in NP I 2 Pick an instance R of yourtavorite NP Complete problem ex 3 in 3SAT I 3 Show a polynomial algorithm to transform R into an instance of Q I Example Clique I CLIQUE ltGkgt G is a graph with a clique of size k I A clique is a subset of vertices that are all connected I Why is CLIQUE in NP I Reduce 3 SAT to Clique I Pick an instance of 3SAT 3 with kclauses I Make a vertex for each literal I Connect each vertex to the literals in other clauses that are not the negation I Any kclique in this graph corresponds to a satisfying assignment


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Kyle Maynard Purdue

"When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the I made $280 on my first study guide!"

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.