D I S
D I S CIS 6930
Popular in Course
Popular in Comm Sciences and Disorders
This 17 page Class Notes was uploaded by Mrs. Rahul Wuckert on Thursday September 17, 2015. The Class Notes belongs to CIS 6930 at Florida State University taught by Staff in Fall. Since its upload, it has received 78 views. For similar materials see /class/205701/cis-6930-florida-state-university in Comm Sciences and Disorders at Florida State University.
Reviews for D I S
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/17/15
A L 1 Review of Complexity Theory Breno de Medeiros Department of Computer Science Florida State University I Review of CompiexityTneory 7 pi Turing Machines M 6 A traditional way to model a computer mathematically is the Turing Machine model TM A Turing Machine is characterized by that A TM recognizes a set of symbols from a finite alphabet 2 Assume that E 01m By a string understand any finite sequence of 0 s and 1 s followed by a u A TM has an halfinfinite tape containing cells Each cell may store an element of E A TM has a set of states S with a special state called start A At the beginning ofa computation TM is at state start an element of S and the tape contains a string A There is a special state Halt Technically NOT an element of S A If the TM solves a decisionalproblem it has also special states YES and NO not part of S either A If the TM solves a computational problem it has an infinite output tape where It may write a string l Breno de Medeiros Florida State University Adv Top Crypt Netw Sec p2 Turing Machine Computations M TM has a tape head At start it lies in the first tape cell TM s computations are described by a state transition function 6 e 6 is a function from E X S to E X S U halt YES NO x gt lt l 6 At each step the TM reads the symbol 0mm in the tape cell at the current tapehead position and its current state 3mm It then computes Macaw 3mm 2 0mm snahposne Then a 0mm is written to the current tape cell and the tape head is moved one cell right left or stays in the same position according to posnem being equal to gt lt or i A The current state is changed to 3mm If 3mm is one of halt YES NO then the computations is concluded 6 If TM has an output tape 6 also specifies an optional symbol to be written to output and the movement of the output tape head Breno de Medelros Florida State University Adv Top Crypt Netw Sec p3 Example of a Turing Machinequot Computation w A AJ 1 W l Breno de Medewros Honda State Unwersny Adv Top Crypt Netw Sec 734 39l Terminology M G Each step of a Turing Machine is given a unitary time cost 6 Let tTM6 be the number of steps taken by a Turing Machine TM to complete processing an input string 6 6 the length of 6 is the number of 0 s and 1 s in the representation of 6 t Breno de Medelros Florida State University Adv Top Crypt Netw Sec p5 Language Accepted by a TuringI Machine M 6 A language L is a subset of 0 1 Considered strings by implicitly appending a terminating u a The language LTM accepted by a turing machine TM is the set of strings that lead to TM terminate in finitely many steps in the state YES The class P polynomialtime contains all languages L such that a Given L there is a Turing Machine TML such that L is the language accepted by TML and moreover a polynomial pTMLn such that if E is in L and g n then tTML 5 S PTML7 L I Breno de Medelros Florida State University Adv Top Crypt Netw Sec p13 Example of a Polynomial Language w A AJ 1 W l Breno de Medewros Honda State Unwersny Adv Top Crypt Netw Sec 737 Nondeterministic Turing Machines M o A nonrealistic computational model that is nonetheless important from a theoretical standpoint is that represented by a nondeterministic Turing Machine NTM o An NTM is similar to a deterministic TM except that instead of a single valued transition function 6 it has a multivalued one 5 At any given step in the computation the machine may choose which of the possible values to take for the transition 3 A string 6 is accepted by an NTM if there is a valid computational path ie set of choices at each step compatible with 5 which lead to NTM terminate in state YES when given 6 as its input at state start and if no valid computational paths lead to NTM terminating in state No when given 6 as input I Breno de Medeiros Florida State University Adv Top Crypt Netw Sec p8 Nondeterministic time M 6 If E is accepted by NTM the time fNTM to process string 6 is by definition the shortest valid computational path leading to NTM accepting E o The complexity class NP is defined as the set of languages that are accepted by a non deterministic machine in polynomial time More precisely Given L there is a non deterministic Turing machine NTML such that L is the language accepted by NTML and a polynomial pNTML such that if is in L and g n then A A ENTMLW S PNTML Breno de Medeiros Florida State University Adv Top Crypt Netw Sec p9 Example of an NP language w A AA r7 4 Breno de Medewros Honda State Unwersny Adv Top Crypt New Sec 7310 Introducing randomization M We have considered deterministic computations as well as nonrealistic nondeterministic ones However in practice one often considers probabilistic computations These computations are like nondeterministic ones in the sense that their transition function is manyvalued but each type oftransition is associated with a probability value Given a probabilistic machine PTM each input string 6 may lead to both accepting and rejecting computational paths The probability of acceptance is the total sum of the probabilities associated to all accepting computational paths Randomized complexity classes are defined in terms ofthe existence of PTM s that accept their languages with specified acceptance and rejection probabilities I Breno de Medelros Florida State University Adv Top Crypt Netw Sec p11 The class RP M 6 RP is the class of languages L such that A There is a probabilistic turing machine PTML and a polynomial ppTML A For every string 6 with g n all computational paths of PTML terminate in at most ppTML n steps A lf does not belong to L then PTML always rejects E A lf belongs to L then the probability that PTML accepts is at least 12 6 Observations A RP contains P as any deterministic Turing Machine TM is also a probabilistic nondeterministic TM satisfying the above probability restrictions A NP contains RP as eliminating the probabilities from PTM gives a nondeterministic machine NTM t Breno de Medeiros Florida State University Adv Top Crypt Netw Sec p12 v RP language example w A AA r7 4 Breno de Medewros Honda State Unwersny Adv Top Crypt New Sec 7313 The classes coRP and Z PP M The definition of RP is not symmetric as the behavior when E is in L or not differ If we invert the definition we have the coRP class containing the languages L such that there is a Turing machine that always accepts if E is in L but rejects with probability at least 12 if E is not in L As before P C coRP The class ZPP is defined as RP coRP P C ZPP and many believe that P ZPP but that has not been proven t Breno de Medeiros Florida State University Adv Top Crypt Netw Sec p14 Another characterization of Z PP M e ZPP can also be characterized by the class of languages that have PTM such that with probability 1 the algorithm will terminate with the correct answer Note that here the answer is guaranteed to be correct always but the running time is not guaranteed to be polynomial only expected to in a probabilistic sense Show the equivalence Breno de Medeiros Florida State University Adv Top Crypt Netw Sec p15 Boundederror ProbabilisticI Polynomial BPP Class M BPP is the class on languages decidable by PTM that finish all instances in polynomial time and have an error at most 13 in all instances Formally A A language L is in BPP if there are a probabilistic Turing machine PTML and polynomial ppTML st PTML takes at most ppTML n steps to process any strings of length n and A lf E L then PTML accepts with probability at least 23 A lf Q L it accepts with probability at most 13 The bound 13 is arbitrary By simulating the PTM on the same input a polynomial number of times and using majority voting one can show that is sufficient to start with error probability 12 1p1n where p1 is any polynomial and then the error can be reduced to e such that log2 6 lt p2n for any polynomial p2 In particular any constant C E 012 can be used instead of 13 Breno de Medelros Florida State University Adv Top Crypt Netw Sec p16 l The Complexity Class PP M o PP is the class of all decision problems solvable in deterministic polynomial time by a PTM with the following error probabilities a If 6 belongs to the language is a YES instance then the PTM accepts with a probability strictly larger than 12 a On a NO instance the algorithm replies YES with probability at most equal to 12 6 For instance SAT is a problem in PP To see this consider a Boolean formula qb in n variables and the following PTM A Choose a random assignment truefase lt x to each of the boolean variables independently A Evaluate qb on the above assignment If true answer YES lf false answer YES or NO with equal probability 12 I Breno de Medeiros Florida State University Adv Top Crypt Netw Sec p17
Are you sure you want to buy this material for
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'