Probabilistic fine structure between P and PSPACE

10 maio 2013, 11:30 • José Félix Costa

Introduction to Monte Carlo and Las Vegas methods. Examples: polynomial identity, matrix multiplication, minimum cut of graphs.

Probabilistic Turing machines.

Class PP.

Proposition: NP included in PP.

Proposition: For every set A in PP, there exists a probabilistic Turing machine that decides A with accepting probability different from 1/2.