Teorema de Savitch

teorema de teoria de complexitat

En teoria de la complexitat, el Teoremoa de Savitch, provat per Walter Savitch el 1970 dona la relació entre complexitats espacials deterministes i no deterministes.[1][2] Diu que per cada funció

Dit d'altre manera, si una màquina de Turing no determinista pot resoldre un problema usant un espai f(n), una màquina de Turing ordinària (determinista) pot resoldre el mateix problema amb el quadrat del dit espai.

Corol·laris del teorema modifica

Es dedueixen importants corol·laris a partir del teorema:

  • PSPACE = NPSPACE
    • Se segueix directament del fet que el quadrat d'una funció polinòmica segueix sent una funció polinòmica. Es creu que no existeix una relació similar entre les classes polinòmiques P i NP, tot i que és encara una qüestió oberta.
  • NLL²
    • Ja que  

Referències modifica

  1. Sanjeev., Arora,. Computational complexity : a modern approach. Cambridge: Cambridge University Press, 2009. ISBN 9780521424264. 
  2. Savitch, Walter J. «Relationships between nondeterministic and deterministic tape complexities». Journal of Computer and System Sciences, 4, 2, 1970-04, pàg. 177–192. DOI: 10.1016/s0022-0000(70)80006-x. ISSN: 0022-0000.