Complexity
Document Summary
Instructors: erik demaine, jason ku, and justin solomon. Decision problems: decision problem: assignment of inputs to yes (1) or no (0, inputs are either no inputs or yes inputs. Decidability: program is nite (constant) string of bits, i. e. , a nonnegative integer n. Nondeterministic polynomial time (np: p is the set of decision problems for which there is an algorithm a such that, for every input. V always runs in time polynomial in the size of i; If i is a yes input, then there is some certi cate c so that v outputs yes on input (i, c); and. If i is a no input, then no matter what certi cate c we choose, v always output no on input (i, c): you can think of the certi cate as a proof that i is a yes input. If i is actually a no input, then no proof should work. Adds the weights on p and checks whether d.
