Complete sets for PP
23 maio 2013, 10:30 • José Félix Costa
Non-deterministic Turing machines as Boolean formulas: The Boolean formula ACCEPT(w)(x_1,...,x_n).
PP-complete sets: MAJ e #SAT. Proof by reduction of #SAT to MAJ.
23 maio 2013, 10:30 • José Félix Costa
Non-deterministic Turing machines as Boolean formulas: The Boolean formula ACCEPT(w)(x_1,...,x_n).
PP-complete sets: MAJ e #SAT. Proof by reduction of #SAT to MAJ.