noc21-cs49-lec18

Name: noc21-cs49-lec18
Uploaded: 2023-12-03T14:16:43.879Z
Duration: 42 min 27 s
Channel: IIT Kanpur July 201
Description: Introduction to probabilistic computations. Definition of probabilistic TMs. Running time, acceptance criterion and difference between NDTMs and PTMs. Definition of the classes BPTIME(T(n)), BPP. Relationship of BPP with respect to other complexity classes such as P, NP and PSPACE.

IIT Kanpur July 201

1 Video View·Dec 3, 2023

Introduction to probabilistic computations. Definition of probabilistic TMs. Running time, acceptance criterion and difference between NDTMs and PTMs. Definition of the classes BPTIME(T(n)), BPP. Relationship of BPP with respect to other complexity classes such as P, NP and PSPACE.