Resultats de la cerca

...om el conjunt de [[Llenguatge formal|llenguatges expressats]] per [[lògica de segon ordre]].<ref>{{Ref-web|url=https://complexityzoo.uwaterloo.ca/Complex == Relació amb d'altres classes == ...

...es [[Recursió primitiva|funcions recursives primitives]] és la unió de les classes<ref>{{Ref-llibre|cognom=E.|nom=Rose, H.|títol=Subrecursion : functions and ...per tant, son dins de NO-ELEMENTARY. Particularment, hi ha problemes a les classes associades a la recursió primitiva que no està a ELEMENTARY. ...

...ió]] que poden ser resolts amb [[Circuit comparador|circuits comparadors]] de mida polinòmica.<ref name=:0>{{Ref-publicació|cognom=Mayr|nom=Ernst W.|cogn ...variable, la seva negada o una constant. Un els fils s'etiqueta com el fil de sortida. ...

...de decisió|problemes de decisió]] que es poden resoldre per una [[màquina de Turing no determinista]] usant una quantitat logarítmica d'espai.<ref>{{Ref ...determinista]] és també una màquina de Turing no determinsita, L està dins de NL. ...

...espai ''O''(''f(n)'') i temps il·limitat. Es la contrapartida determinista de la classe [[NSPACE]].<ref>{{Ref-llibre|cognom=Michael.|nom=Sipser,|títol=In Diverses classe de complexitat es defineixen en funció de DSPACE: ...

...eople.cs.uchicago.edu/~fortnow/papers/gaps.ps|títol=Gap-definable counting classes|consulta=2019-01-08|nom=S. Fenner, L. Fortnow, S. Kurtz|editor=Journal of C * si la resposta és «no», llavors la diferència entre el nombre de camins que accepten i que rebutgen és no negatiu i com a mínim <math>2^{-po ...

...n [[complexitat de circuits]]. És la primera classe de la jerarquia de les classes TC.<ref>{{Ref-publicació|cognom=Hesse|nom=William|cognom2=Allender|nom2=Eri ...majoria. Equivalentment, es poden usar portes de llindar enlloc de portes de majoria. ...

...polinòmic de portes [[Porta AND|AND]], [[Porta OR|OR]] i [[Porta NOT|NOT]] de fan-in il·limitat.<ref name="worldcat.org">{{Ref-llibre|cognom=Sanjeev.|nom ...zades de manera alternativa i a les [[Màquina de Turing alternant|màquines de Turing alternants]].<ref>{{Ref-llibre|cognom=J.|nom=ATALLAH, MIKHAIL|títol= ...

...de decisió|problemes de decisió]] que poden ser resolts amb una [[màquina de Turing]] usant un espai polinòmic.<ref>{{Ref-llibre|cognom=Michael.|nom=Sip ...uring usant ''O''(''t''(''n'')) d'espai per alguna funció ''t'' de la mida de l'entrada ''n'', llavors es pot definir PSPACE com ...

...ndau|notació de O gran]], ''f'' és una funció qualsevol i ''n'' és la mida de l'entrada.<ref>{{Ref-llibre|cognom=Michael.|nom=Sipser,|títol=Introduction ...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 accepta ...

...mps il·limitat. Es la contrapartida no determinista de la classe [[DSPACE (Complexitat)|DSPACE]].<ref>{{Ref-llibre|cognom=Michael.|nom=Sipser,|títol=Introduction Diverses classe de complexitat es defineixen en funció de DSPACE: ...

...enguatge]] ''L'' és a '''S{{su|p=''P''|b=2}} si existeix un predicat ''P'' de [[temps polinòmic]] tal que:''' on ''y'' i ''z'' son polinomis de ''x.'' ...

...ats perquè es correspon amb un recurs real força important com és el temps de còmput.<ref>{{Ref-llibre|títol=Computational complexity theory|url=https:// ...la classe de complexitat DTIME(f(n)). No hi ha restricció en la quantitat de memòria utilitzada, però pot haver-hi restriccions en d'altres recursos. ...

...-Wesley|lloc=Reading, Mass.|isbn=0201530821}}</ref> Formalment, la màquina de Turing te dues cintes, una per codificar l'entrada i només es pot llegir i == Relacions amb d'altres classes == ...

...s de moneda d'Arthur, ja que fa el llançament després de rebre el missatge de Merlin.<ref name=:0>{{Ref-llibre|cognom=Sanjeev.|nom=Arora,|títol=Computati ...M'' i uns polinomis ''p'' i ''q'' tals que per cada cadena d'entrada ''x'' de longitud ''n'' = |''x''|, ...

...lemes que son PSPACE-complet es poden veure com els problemes més difícils de la [[PSPACE|classe PSPACE]].<ref>{{Ref-llibre|cognom=Michael,|nom=Sipser,|t ...força exemples de jocs i trencaclosques que entren dins aquesta classe de complexitat.<ref>{{Ref-web|url=https://www.ics.uci.edu/~eppstein/cgt/hard.html|títol=Co ...

...s de decisió que es poden resoldre en [[temps polinòmic]] en una [[màquina de Turing no ambigua]] per almenys un camí que accepte per cada entrada.<ref>{ ...Més formalment, un llenguatge ''L'' pertany a UP si existeix un algorisme de dues entrades i temps polinòmic A i una constant c tal que: ...

...e és igual a la que considera [[Màquina de Turing no determinista|màquines de Turing no deterministes]]. Quan es restringeix ''p''(''n'') a una funció li En termes de [[DSPACE (Complexitat)|DSPACE]] es té ...

...r resolts amb una [[màquina de Turing no determinista]] en espai [[Notació de Landau|O]] (2^''p''(''n'')), on ''p''(''n'') és una [[Funció poli En termes de [[NTIME (Complexitat)|NTIME]] es té ...

...ecursos fitats de la [[jerarquia aritmètica]] i la [[jerarquia analítica]] de [[lògica matemàtica]].<ref>{{Ref-llibre|cognom=Sanjeev.|nom=Arora,|títol=Co Hi ha múltiples definicions equivalents de les classes de la jerarquia polinòmica. ...