CS341 Study Guide - Eulerian Path, Or Gate, Program Counter

63 views4 pages
21 Dec 2014
Course
Professor

Document Summary

References for today"s lecture: clr, sections 34. 3, 34. 4, 34. 5. We now modify the notion of reduction introduced in lecture 20 to take into account the amount of time required for the reduction. We consider only decision problems, that is, problems with yes/no answers. In other words, if x is an instance of decision problem a, then f(x) is an instance of decision problem b, and the answer to x must be the same as f(x). We can view f as a kind of translation. Imagine we have a box b that answers questions posed to it in french, but we have questions we want to pose in english. We take the question x and apply f(x), which translates english questions to. Then we ask b to answer the question f(x); by doing so it answers the question x. If a and b are decision problems, and b is in p, and a p b, then a is in p.

Get access

Grade+20% off
$8 USD/m$10 USD/m
Billed $96 USD annually
Grade+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
40 Verified Answers

Related Documents