NTIME (Complexitat)

De Viquipèdia
Salta a la navegació Salta a la cerca

En teoria de la complexitat, la classe de complexitat NTIME(f(n)) és la classe dels problemes de decisió que es poden resoldre per una màquina de Turing no determinista en un temps O(f(n)), on O és la notació de O gran, f és una funció qualsevol i n és la mida de l'entrada.[1][2]

Això vol dir que pel problema donat, una màquina de Turing no determinista per una entrada de mida n funcionarà un temps O(f(n)) i sempre s'aturarà i acceptarà o rebutjarà l'entrada.[3]

L'espai disponible per la màquina no està limitat, tot i que no pot sobrepassar O(f(n)), ja que el temps disponible limita l'espai que es pot utilitzar.

Relacions amb d'altres classes[modifica]

La classe de complexitat NP es pot definir en termes de NTIME com segueix:

De forma similar, la classe NEXP es defineix en termes de NTIME:

NTIME està relacionada amb DSPACE de la següent manera: per cada funció construïble f(n) es te

Una generalització de NTIME és ATIME, definida amb màquina de Turing alternativa i resulta que

Referències[modifica]

  1. Michael., Sipser,. Introduction to the theory of computation. 3rd ed. Boston, MA: Cengage Learning, 2013. ISBN 9781133187790. 
  2. Peter., Linz,. An introduction to formal languages and automata. 5th ed. Sudbury, MA: Jones & Bartlett Learning, 2012. ISBN 9781449615529. 
  3. «Complexity Zoo:N - Complexity Zoo» (en anglès). [Consulta: 29 novembre 2018].