P (complessità)

Abbozzo
Questa voce sull'argomento teorie dell'informatica è solo un abbozzo.
Contribuisci a migliorarla secondo le convenzioni di Wikipedia.
Diagramma di Eulero-Venn per le classi di complessità P, NP, NP-completo e NP-hard

Nella teoria della complessità computazionale, P, anche conosciuto come PTIME o DTIME(nO(1)), è una delle più importanti classi di complessità. Contiene tutti i problemi decisionali che possono essere risolti da una macchina di Turing deterministica usando una quantità polinomiale di tempo di computazione, o tempo polinomiale.

La tesi di Cobham asserisce che P è la classe di problemi computazionali che sono "risolvibili efficientemente" o "trattabili"; in pratica, qualche problema che non si sa essere in P ha soluzioni pratiche, e qualche problema in P non ne ha.

Definizione

Un linguaggio L è in P se e solo se esiste una macchina di Turing deterministica M tale che

  • M viene eseguita in tempo polinomiale per tutti gli input
  • Per tutti gli x in L, M restituisce in output 1
  • Per tutti gli x non in L, M restituisce in output 0

P può anche essere vista come una famiglia uniforme di circuiti booleani. Un linguaggio L è in P se e solo se esiste una famiglia di circuiti booleani a tempo polinomiale uniforme { C n : n N } {\displaystyle \{C_{n}:n\in \mathbb {N} \}} , tale che

  • Per ogni n N {\displaystyle n\in \mathbb {N} } , C n {\displaystyle C_{n}} prende n bit come input e restituisce 1 bit in output
  • Per ogni x in L, C | x | ( x ) = 1 {\displaystyle C_{|x|}(x)=1}
  • Per ogni x non in L, C | x | ( x ) = 0 {\displaystyle C_{|x|}(x)=0}

Problemi notevoli in P

Si sa che P contiene molti problemi naturali, incluse le versioni decisionali di programmazione lineare, calcolare il massimo comun divisore e trovare la corrispondenza massima. Nel 2002 è stato mostrato che il problema del determinare se un numero è primo è in P[1]. La classe relativa di problemi funzionali è FP

Diversi problemi naturali sono completi per P, inclusa la raggiungibilità su grafi[2]. L'articolo su problemi P-completi lista ulteriori problemi rilevanti in P.

Note

  1. ^ Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "PRIMES is in P", Annals of Mathematics 160 (2004), no. 2, pp. 781–793.
  2. ^ Neil Immerman, Descriptive Complexity, New York, Springer-Verlag, 1999, ISBN 0-387-98600-6.
  Portale Informatica
  Portale Matematica