Portal de Periódicos da CAPES

Feasible arithmetic computations: Valiant's hypothesis

1987; Elsevier BV; Volume: 4; Issue: 2 Linguagem: Inglês

10.1016/s0747-7171(87)80063-9

1095-855X

Joachim von zur Gathen,

semigroups and automata theory

An account of Valiant's theory of p-computable versus p-definable polynomials, an arithmetic analogue of the Boolean theory of P versus NP, is presented, with detailed proofs of Valiant's central results.