cyanic-selkie/wikianc huggingface dataset:
Lenga Lenga - Gueiteiros de Sendin
Lenga Lenga - Gaiteiros de Sendin, ye un grupo de música tradecional mirandesa, fomenta la passaige de l mais amportante teçtemunho tradecional de ls sous antepassados na Lhéngua, ne ls Cantares, na coreografie de danças mistas i de ls pouliteiros. Garantindo la cuntenidade de la tradiçon cultural de l Praino Mirandés, que tubo an grande risco de stinçon.
Ls trajes cun que l grupo se apersenta son de cunfeçon tradecional a l'eimaige de ls bielhos gueiteiros mirandeses.
Ls strumientos son outénticas réplicas ousados de la época, mantenendo la sonoridade timbríca, cumo na sue ournamentaçon sterna. Fieles a la melodie tradecional, trabalhando ls ritmos i l timbre oural de la lhéngua mirandesa!
Formou-se an 19 de Júlio de 2000, einicialmente cumo trio tradecional, la formaçon atual ye de quatro eilemientos, tenendo cumo oubjetibos zambolber l repertório Mirandés studando, arrecolhendo i criando nuobos temas tradecionales, ancentibando assi l gusto pula gaita de fuolhes mirandesa, fraita pastoril (trés buracos), cantigas tradecionales, remanses i danças de ls pouliteiros.
Ls Eilemientos:
Çcografie
'''
Lhigaçones
'''
Catadorie:Bandas de Pertual Catadorie:Fulclore de Pertual Catadorie:Lhéngua mirandesa Catadorie:Miranda de l Douro
Probedor de Justícia Ouropeu
La funçon de Probedor de Justícia Ouropeu fui anstituída pul Tratado de la Ounion Ouropeia de Maastricht (Países Baixos) an 1992 (Art. 195). L Probedor de Justícia (sede an Strasburgo, Fráncia) atua cumo mediador i ombudsman (probedor) antre ls cidadanos i la admenistraçon de la Ounion Ouropeia. Ten cumpeténcias para recebir i ambestigar queixas apersentadas por qualquiera cidadano, ampresa ó anstituiçon de la Ounion Ouropeia ó qualquiera pessona singular ó coletiba que more ó tenga la sue sede statutária nun paíç de la Ounion Ouropeia.
Las queixas puoden ser apersentadas por carta simples ó por un formulairo de queixa eiletrónico an qualquiera de las 23 lhénguas oufeciales de la Ounion Ouropeia. Zde 1 de janeiro de 2000 até 31 de dezembre de 2003, l Probedor de Justícia recebiu 8549 queixas, antre eilhas cerca de 30% anserian-se na sfera de l mandato de l'uorgano. L mais de las queixas dízen respeito a causos de mala admenistraçon por parte de la Comisson Ouropeia i la falta de trasparéncia. Ls países d'adonde ben l mais de las queixas son de la Almanha, Spanha, Fráncia i Eitália.
L Probedor de Justícia ye eileito pul Parlamiento Ouropeu por un período renobable de cinco anhos, que corresponde a ua lhegislatura de l Parlamiento Ouropeu. An 1995, l finlandés Jacob Söderman fui eileito l purmeiro Probedor de Justícia Ouropeu atuando até 2003. Nikiforos Diamandouros, anterior Probedor de Justícia de la Grécia, assumiu l cargo an 1 de Abril de 2003 i fui reileito an Janeiro de 2005 para un mandato de cinco anhos.
Paltoga
thumb|right|250px|Paltoga
Paltoga (Палтога an russo) ye űa cidade de la Rússia.
Aeroporto Con Dao
240px|thumb|right|Aeroporto Con Dao L Aeroporto Con Dao (Sân bay Côn Đảo) i cun un aeroporto doméstico, lhocalizado ne l çtrito de Con Son, l’aeroporto Con Dao ye ua strutura que ten atualmente ua pista asfaltada de 1278 metros de cumprimiento cun 30 metros d'anchura, situado a 2 quilómetros ne l norte de la cidade de Con Son, província Ba Ria-Vung Tau, Vietnam. Queda a 360 km norte de la cidade de Ho Chi Minh Cidade. Vietnam Air Services Company i l quarto stá reserbado para bóos pribados. L aeroporto de Con Son ye l segundo an tráfego aéreo de l Vietnam, Cidade de Ho Chi Minh.
Paltoga
Catadorie:Cidades de la Rússia
Reloijo
250px|thumb|right| Macanismo dun reloijo-outomático de pulso L reloijo ye outelizado cumo medidor de l tiempo zde la Antiguidade, an bariados formatos. Ye ua de las mais antigas ambençones houmanas.
Stória
Ls mais antigos éran ls reloijos de sol, probablemente ousados puls gnómons. La stória registra qu'apareciu na Judeia, mais ó menos an 600 a.C., culs reloijos d'auga (clepsidras) i ls reloijos d'arena (ampulhetas). L'arcebispo de Berona chamado Pacífico, an 850 de la nuossa era, custruiu l purmeiro reloijo macánico baseado an angrenaiges i pesos. An 797 (ó 801), l califa de Bagdade, Harun al-Rashid, persenteou Carlos Magno cun un alifante asiático chamado Abul-Abbas, junto cun un reloijo macánico d'adonde saía un páixaro qu'anunciaba las horas. Esso andica que ls purmeiros reloijos macánicos probablemente fúrun ambentados puls asiáticos. Assi i todp, ambora eisista cuntrobérsia subre la custruçon de l purmeiro reloijo macánico, l papa Silbestre II ye cunsidrado sou ambentor. Outros grandes custrutores i aperfeiçoadores de reloijos fúrun Ricardo de Walinfard (1344), Santigo de Dondis (1344), sou filho João de Dondis que quedou coincido cumo "Horologius", i Anrique de Bick (1370).
Por buolta de 1500, Pedro Heinlein, na cidade de Nuremberga, fabrica l purmeiro reloijo de bolso.
Ls mais percisos son ls atómicos.
Ls purmeiros reloijos outelizados fúrun ls reloijos de bolso. Éran mui ralos i tenidos cumo berdadeiras jóias, pus poucos tenien un. Ls reloijos de bolso éran simblo de l'alta aristocracie.
Comenta-se que fui Santos Dumont quien ambentou ls reloijos de pulso. L'amisade de Santos Dumont cun Louis Cartier benie de la fin de l seclo XIX. Ua nuite, Alberto dixo-le que nun tenie cumo ler l'hora an pleno bolo an sou reloijo de bolso; cula ajuda de l mestre relojeiro Edmond Jaeger, Cartier apersentou ua soluçon para Santos Dumont, un protótipo de l reloijo de pulso, an 1904, l qual premitie ber las horas mantenendo las manos ne ls quemandos.
250px|thumb|right| Modelo carrilhon de mesa bastante antigo 250px|thumb|right| Reloijo de pulso 250px|thumb|right| Reloijo de parede 250px|thumb|right| Reloijo degital de mesa
Catadorie:Strumientos de medida Catadorie:Mediçon de l tiempo Catadorie:Oujetos
Kurt Gödel
Kurt Friedrich Gödel (an alman, pronuncia-se 10px ouça ) (Brunn, Áustria-Hungrie, 28 de Abril de 1906 — Princeton, Stados Ounidos, 14 de Janeiro de 1978) fui un matemático austríaco, naturalizado amaricano.
L trabalho mais coincido de Gödel ye sou teorema de l'ancumpletude, ne l qual afirma que qualquiera sistema axiomático suficiente para ancluir l'aritmética de ls númaros anteiros nun puode ser a la par cumpleto i cunsistente. Esto senefica que se l sistema ye outo-cunsistente, anton eisistiron proposiçones que nun poderán ser nin cumprobadas nin negadas por este sistema axiomático. I se l sistema fur cumpleto, anton el nun poderá balidar la si mesmo — serie anconsistente.
Bida
Natural de Brunn, porbíncia austro-húngara de la Morábia (hoije Brno, na República Tcheca), filho dun gerente de fábrica téxtil. Kurt era coincido na família cumo Dar Heirr Warun (Sr. Por qué?), por cunta de l grande númaro de preguntas que fazie.
Segundo l sou armano, Kurt tubo ua anfáncia feliç, mesmo sendo tímido i se aborrecendo facilmente. Fui batizado dues sumanas passado sou nacimiento cumo protestante luterano, segundo la religion de la mai, tenendo Friedrich Redlich cumo padrino i anspiraçon para sou segundo nome.
La purmeira guerra mundial nun l'atingiu diretamente, Brunn staba bien loinge de las zonas de batailha. Mas, an 1918, cul stablecimiento de la Tchecoslobáquia cumo nacion, houbo un eisolamiento de a minorie que falaba alman na cidade. Kurt renunciarie an 1929 a la cidadanie tcheca, tornando-se austríaco ouficialmente.
An 1923 cuncluiu, cun agabon, l curso fundamental na scuola almana de Brunn i ambora tubisse eicelente talento para lenguaiges, el se aperfundou an Stória i Matemática. Sou antresse pula Matemática oumentou an 1920, quando acumpanhou Rudolf, sou armano mais bielho, que fura para Biena cursar la Scuola de Medecina de la Ounibersidade de Biena. An sue adolescéncia, studou Goethe, l manual de Gabelsberger, la teorie de las quelores de Isaac Newton i las "Críticas" de Kant.
Studo an Biena
Ambora einicialmente pretendisse studar Física Teórica, als 18 anhos, el frequentou cursos de Matemática i Filosofie, cunseguindo lougo l mestrado an Matemática. Nessa época el adotou las eideias de l rialismo matemático. Leu la 'Metaphysische Anfangsgrunde Dar Naturwissenschaft', de Kant i participou de l Círclo de Biena juntamente cun Moritç Schlick, Hanes Hahn, i Rudolf Carnap. Kurt studaba la teorie de ls númaros quando participou dun seminairo cun Moritç Schlick subre la "Antrodution to Mathematical Philosophy", de Bertrand Russell, i antressou-se eimediatamente pula lógica matemática.
Nessa época de grande atebidade, conheciu sue fetura mulhier Adele Nimbursky (nacida Porkert), ampeçou a publicar scritos subre lógica i frequentou aulas de David Hilbert, an Bolonha, subre la cumpletude i cunsisténcia de sistemas matemáticos.
An 1929 Gödel tornou-se cidadano austríaco i cumpletou sue dessertaçon para doutoramiento sob la superbison de Hanes Hahn, adonde stableciu la cumpletude de l cálclo de predicados de purmeira orde, tamien coincido cumo Teorema de la cumpletude de Gödel.
Trabalho an Biena
An 1930, graduou-se 'Doutor an Filosofie' i porduziu ua berson cumbinada de sous scritos subre la cumpletude, la qual fui publicada pula Academie de Ciéncias de Biena. An 1931 publicou sou famoso teorema de l'ancumpletude ne l 'Uber formal unentscheidbare Sätze dar Principia Mathematica und berwandter Systeme'. Neste scrito el demunstrou que qualquiera sistema matemático axiomático, suficiente para ancluir l'aritmética de ls númaros naturales, necessariamente:
Estes dous teoremas ancerrórun cientos d'anhos de tentatibas de stablecer un cunjunto cumpleto d'axiomas que possibelitassen deduzir to la Matemática cumo l "Principia Mathematica" ó ne l formalismo de Hilbert. Esso tamien amplica qu'un cumputador jamales puoda ser porgramado para respunder todas las questones matemáticas.
An 1932 fui diplomado pula Ounibersidade de Biena i, an 1933, tornou-se "Pribatdozent" (docente nun remunerado).
Bejita a la América de l Norte
Nesse mesmo anho de 1933, biajou pa la América. Alhá, ancuontrou Albert Einstein i anscrebiu-se na cunferéncia anual de la Amarican Mathematical Society. Durante astanho el zambolbiu las eideias de cumputabelidade i de las funçones recursibas cul propósito de lecionar subre las funçones recursibas gerales i l cunceito de berdade matemática. Este trabalho fui zambolbido na ária de la teorie de ls númaros usando la custruçon de ls númaros de Gödel.
Gödel besitou l IAS outra beç ne l outonho de 1935. La biaige fui defícel i saustiba, resultando nua recaída depressiba.
Boltou a lecionar an 1937 i durante esse anho trabalhou arduamente na proba de la cunsisténcia de la 'Heipótese de l Cuntinun'. An 20 de setembre de 1938 casou-se cun Adele. Lougo passado besitou outra beç l IAS i, na primabera de 1939, la University of Notre Dame.
An 1938 anunciou la demunstraçon de la cunsisténcia relatiba de l Axioma de la Scolha, la Heipótese Generalizada de l Cuntino i outros enunciados, sob l suposto de que ls axiomas de la Teorie de Cunjuntos (sin l Axioma de la Scolha) son cunsistentes, mas la proba cumpleta solo será publicada an 1940. Esse trabalho cuntribui pa l sclarecimiento de l purmeiro Porblema de Hilbert.
Trabalho an Princeton
Passado aneixaçon de la Áustria pula Almanha, an 1938, l títalo de "Pribatdozent" de Gödel fui zaparecido i el fui cumbocado la se cunscrebir ne l Eisercito Nazista. An Janeiro de 1940, el i sue mulhier saíran de la Ouropa atrabeç de la camino de fierro tras-siberiana i biajórun pula Rússia i Japon, até chegáren a la América de l Norte an 4 de márcio de 1940. Stablecírun-se an Princeton, quando Gödel recebiu grande apoio de Norbert Wiener i passou a antegrar l IAS. Nessa época, boltou-se pa la Filosofie i Física, studando detalhadamente ls trabalhos de Gottfried Leibniç, Kant i Edmund Husserl.
Ne l final de 1940 demunstrou l'eisisténcia de la soluçon paradoxal de las eiquaçones de campo de la teorie giral de la relatebidade de Albert Einstein. Cuntinando sous trabalhos an lógica, ne l mesmo anho, publicou l studo subre la 'cunsisténcia de l'axioma de la scolha i de l'heipótese de l cuntinun generalizada culs axiomas de la teorie de ls cunjuntos', l qual tornou-se un de ls assuntos clássicos de la Matemática Moderna.
An 1946 Gödel tornou-se nembro permanente de l IAS i an 1948 naturalizou-se cidadano stadunidense. Passou a porsor pleno de l'anstituto an 1953 i porsor emérito an 1976. Ne l'ampeço de la década de 1970, Gödel çtribuiu als amigos un studo de la proba ontológica de l'eisisténcia de Dius eilaborada por Gottfried Leibniç, l qual acabou sendo coincido cumo "proba ontológica de Gödel".
Kurt Gödel recebiu muitos prémios i honraries durante sue bida i tamien l purmeiro Prémio Albert Einstein, an 1951. An 1974 recebiu la Medalha Nacional de Ciéncia. Ne l final de sue bida, Gödel acraditaba star sendo ambenenado i recusaba-se a comer, falecendo an 14 de janeiro de 1978, an Princeton.
Ligaçones sternas
Catadorie:Matemáticos de la Áustria Catadorie:Matemáticos de ls Stados Ounidos Catadorie:Matemáticos de l seclo XX Catadorie:Muortes por fame Catadorie:Naturales de Vrno
Sacaben
Sacaben (an lhéngua pertuesa Sacavém) ye ua freguesie i cidade pertuesa de l cunceilho de Loures, cun 3,81 km² de ária i 17 659 habitantes (2001). Densidade: 7,4 hab/km².
Catadorie:Pertual
Voyage, Voyage
"Voyage Voyage" ye ua cançon de 1986 scrita por Jean-Michel Ribat, grabada pula cantora francesa Desireless i regrabada por Kate Ryan i tamien por Sarah Brightman. Fui l purmeiro single de l sou álbun, François i se tornou un grande sucesso an muitos países de la Ouropa.
An 2007, la cantora belga Kate Ryan tamien lhançou ua berson de la cançon.
Catadorie:Música Catadorie:Desireless
Áustria
thumb|right|200px|[[Bandeira de la Áustria]] 200px|right thumb Áustria ye un paíç de cerca de 9,1 milhones d'habitantes (2023), lhocalizado na Ouropa Central.
Desireless
Desireless, nome artístico de Claudie Fritsch-Mentrop, (Paris, 25 de dezembre de 1952) ye ua cantora francesa d'ourige checa. Antre 1986 i 1988, sue mais famosa cançon "Voyage Voyage" quedou ne l topo de las paradas an praticamente to l mundo, sendo un de ls ícones de ls anhos uitenta.
Catadorie:Música
Áustria
Catadorie:Paízes de la Ouropa
Lhista de reis de Lhion
thumb|right|150px| Armas de l Reino de Lhion L reino mediebal de reino de Lhion tubo la sue ourige na trasferéncia de la capital de l reino de las Astúrias de Obiedo pa la cidade de Lhion, ne ls tiempos de Fonso III de las Astúrias. Mais tarde, por sue muorte, este rei debediu l sou reino antre ls sous trés filhos: Fruela II gobernou nas Astúrias, Ourdonho II na Galiza, i Garcia I an Lhion; pulas sues muortes sucessibas, todos benerien a reinar subre l reino de Lhion.
Antidade heigemónica, por alguns períodos de tiempo l reino de Lhion se debediu noutros bários reinos (Castielha, Galiza, Pertual), para depuis se buoltar a unificar (fuora Pertual, que nun mais boltou a la sue órbita); stinguiu-se an 1230, quando fui defenitibamente absorbido por Castielha; zde anton ls reis daquel reino fúrun tamien reis de Lhion.
Dinastie de Nabarra ó Ximena (1037-1126)
Depuis de derrotar las tropas leonesas i de la muorte de l rei Bermudo III, Fernando I, que yá era rei de Castielha (que se outonomizara de cundado an reino xefiado puls reis de Nabarra), acediu al trono de Lhion; l sou dreito fundamentaba-se ne l casamiento cumo Sancha, armana de Bermudo; trata-se de la purmeira unificaçon de ls tronos de Lhion i Castielha.
Depuis de la muorte de Fernando, l reino fui repartido puls sous trés filhos, Garcia (Galiza), Sancho (Castielha) i Fonso (Lion).
Dinastie de la Borgonha (1126-1230)
Depuis de la muorte de Fonso VII, l reino fui repartido puls sous dous filhos, Fernando (Lion) i Sancho (Castielha i Toledo).
Passado la muorte de Fonso IX, l sou filho Fernando, yá rei de Castielha (hardança materna), heirdou tamien la corona de Lhion, anque l sou pai l tener zerdado an fabor de las filhas Sancha i Dulce. Pul acuordo de paç firmado por mediaçon de la sue mai, Santa Teresa de Pertual, estas renunciórun al trono an fabor de l meio-armano; fui anton que se dou a unificaçon defenitiba de las corona de Lhion i Castielha, mantendo-se ambora ls prebilégios, foros i questumes própios de cada reino an apartado.
Dinastie de la Borgonha (restouraçon: 1284-1285 i 1296-1301)
Surgiran inda nuobas tentatibas d'outonomizar l bielho reino de Lhion. L sucessor de Fernando III, l célebre Fonso X, l Sábio, zerdou an 1282 l sou segundo filho (l feturo Sancho IV de Castielha), cun quien se inimistara, atribuindo al nieto que tenie tenido de l sou baran mais bielho, Fernando de La Cerda, la corona de Castielha, i al sou filho terceiro, João de Castielha, la corona de Lhion. Por muorte de l rei, Sancho faç-se coroar, contra l stablecido an testamiento, rei de Lhion i Castielha, i l sou armano João declara-se rei de Lhion. Assi i todo, Sancho domina la situaçon, i solo depuis de la sue muorte, l'anfante D. João, aprobeitando la menoridade de Fernando IV de Castielha, goberna de fato Lhion cumo reino outónomo.
Dinastie de Lencastre (1371-)
La lista prossegue cun Lista de reis de Castielha.
Catadorie:Reino de Lhion Lhion
Alla Pugacheva
Eilha repersentou la Rússia ne l Festibal Ourobison de la Cançon 1997 cula cançon "Primadonna" que treminou an 15.º lhugar, tenendo recebido un total de 33 puntos. Passado l festibal, quedou coincida na Ouropa por un cúrtio período de tiempo.
Ligaçones sternas
Catadorie:Música Catadorie:Biografies
Moshchena
thumb|left|250px|Moshchena
Moshchena ye ua cidade de Oucránia.
Aeroporto Dong Tac
240px|thumb|right|Aeroporto Đông Tác L Aeroporto Dong Tac (Sân bay Đông Tác) i cun un aeroporto doméstico, lhocalizado ne l çtrito de Dong Tac, l’aeroporto Dong Tac ye ua strutura que ten atualmente ua pista asfaltada de 3000 metros de cumprimiento cun 45 metros d'anchura, situado a 30 quilómetros ne l norte de la cidade de Tuy Hoa, província Phu Yen, Vietnam. Queda a 540 km norte de la cidade de Ho Chi Minh Cidade. Vietnam Airlines i l quarto stá reserbado para bóos pribados. L aeroporto de Dong Tac ye l segundo an tráfego aéreo de l Vietnam, Cidade de Ho Chi Minh, [[Hanoi].
Catadorie:Aeroporto Vietnam
E-Prime
E-Prime (el quier dezir English Prime) ye un modo de parlar anglés sin ousage l berbo "ser", an anglés to be, an qualcunque modo (be, is, am, are, was, were, been, being ). An su lhoco, un parlador ó un scriptor d'E-Prime ousa berbos diferente cumo "debenir" (an anglés to become), "remaner/restar" (to remain), i "eiqualar" (to equal) ó illes puoden riarrangiar la frase de modo a monstrar que ó qui face l'açon. Per eisemplo, an E-Prime, un scriptor cambiaria l'einunciaçon Mistakes were made = "Errores fuiron facidos" a Joe made mistakes = "Joe faziu errores". Este cambio an formulaçon rebela un ator (Joe) durante que la forma precedente subnegaba l'ator. Ls ousadores d'E-Prime cunsiderian plus adequada la cambiada frase.
Raçones d'E-Prime
Studentes de Semántica General i ousadores d'E-Prime cuntenden que dicer This cat is soft = "Este cato ye suabe" omite numerosos outros atributos, i implica que l'"oubjeto" eisterior del cato ye l "mesme que" l'eisperiéncia anterior de "siendo suabe". An su lhoco, ousadores d'E-Prime dicen This cat feels soft TO ME = "Este cato impressona suabe A ME" de modo a recolliger-se del sequentes:
Que non ye E-Prime
E-Prime i Semántica General non son lhénguas ó formas d'anglés diferente. An su lhoco, illos probide modos diferente de pensar i de parlar del mundo.
Lhénguas cumo arabe, turco, i cantonés, ben que non ténen un berbo separado para "ser", illos ténen l'idia de "siendo". Per eisemplo, un parlante de lhéngua mirandesa puoderia dicer "Este pomo ye rubie". Un parlante d'arabe puoderia dicer "Este pomo rubie". La majoridade del lhénguas puode ser ousada de modo a eisprimer l'idia dun rubie pomo. Un ousador d'E-Prime puode mermente dicer que "Este pomo appare rubie a me" de modo a recolliger-se que "bidente de rubie" anbolbe i l pomo i l'oculo i cerebro del presona reguardante l pomo.
Numerosos anseniadores d'anglés ancoragian studentes a ousar berbos diferente ab "ser". A illes, ousage de berbos plus atibe face oubra scribida plus clar i plus anteressante. Estes anseniadores bolen a afinar oubras scribidas de lor studentes i non necessarimente acesen al idias de Semántica General ó E-Prime.
Notas
Catadorie:Lhéngua anglesa
Aeroporto Phu Cat
240px|thumb|right|Aeroporto Phù Cát L Aeroporto Phu Cat (Sân bay Phù Cát) i cun un aeroporto doméstico, lhocalizado ne l çtrito de Phù Cát, l’aeroporto Phu Cat ye ua strutura que ten atualmente ua pista asfaltada de 3000 metros de cumprimiento cun 45 metros d'anchura, situado a 30 quilómetros ne l norte de la cidade de Quy Nhon, província Bình Định, Vietnam. Queda a 660 km norte de la cidade de Ho Chi Minh Cidade. Vietnam Airlines i l quarto stá reserbado para bóos pribados. L aeroporto de Ca Mau ye l segundo an tráfego aéreo de l Vietnam, Cidade de Ho Chi Minh.
Catadorie:Aeroporto Vietnam
Cumplexidade cumputacional
La teorie de la cumplexidade cumputacional ye un galho de la teorie de la cumputaçon an ciéncia de la cumputaçon teórica i matemática que se cuncentra an classeficar porblemas cumputacionales d'acuordo cun sue deficuldade inerente, i relacionar essas classes antre si. Neste cuntesto, un porblema cumputacional ye antendido cumo ua tarefa que ye, an percípio, passible de ser resolbida por un cumputador (l que basicamente senefica que l porblema puode ser çcrito por un cunjunto d'anstruçones matemáticas). Anformalmente, un porblema cumputacional cunsiste d'anstáncias de l porblema i soluçones para essas anstáncias de l porblema. Por eisemplo, l teste de primalidade ye l porblema de detreminar se un dado númaro ye primo ó nó. Las anstáncias deste porblema son númaros naturales, i la soluçon para ua anstáncia ye si ó nó, dependendo se l númaro ye primo ó nó.
Campos antimamente relacionados cula ciéncia de la cumputaçon teórica son la análeze d'algoritmos i la teorie de la cumputabelidade. Ua çtinçon chabe antre l'análeze d'algoritmos i teorie de la cumplexidade cumputacional ye que la purmeira ye dedicada a analisar la cantidade de recursos necessairos para un detreminado algoritmo resulber un porblema, anquanto l segundo faç ua pregunta mais giral subre todos ls possibles algoritmos que puoden ser ousados para resulber l mesmo porblema. Mais percisamente, el tenta classeficar ls porblemas que puoden ó nun puoden ser resolbidos culs recursos debidamente restritos. Por sue beç, ampondo restriçones subre ls recursos çponibles ye l que çtingue la cumplexidade cumputacional de la teorie de la cumputabelidade: la segunda pregunta que tipos de porblemas puoden, an percípio, ser resolbidos atrabeç d'algoritmos.
Porblemas Cumputacionales
thumb|200px|Un camino ótimo pa l cacheiro biajante passando pulas 15 maiores cidades de la Almanha. Ye l menor camino antre las 43.589.145.600 possibelidades de se bejitar cada cidade satamente ua única beç.
Anstáncias de Porblema
Un porblema cumputacional puode ser bisto cumo ua coleçon anfenita de anstáncias an cunjunto cun ua soluçon para cada anstáncia. La sequéncia d'antrada para un porblema cumputacional ye referido cumo ua anstáncia de l porblema, i nun debe ser cunfundido cul porblema an si. Na teorie de la cumplexidade cumputacional, un porblema se refire a la queston abstrata para ser resolbido. An cuntreste, ua anstáncia deste porblema ye ua spresson cuncreta, que puode serbir cumo antrada para un porblema de decison. Por eisemplo, cunsidre l porblema de teste de primalidade. L'anstáncia ye un númaro (por eisemplo, 15) i la soluçon ye "si" se l númaro ye primo i "nó" se fur l cuntrairo (neste causo "nó"). Altarnatibamente, l'anstáncia ye ua antrada special pa l porblema, i la soluçon ye la salida correspondente a l'antrada.
Para rialçar inda mais la defrença antre un porblema i ua anstáncia, cunsidre la seguinte anstáncia de la berson de decison de l porblema de l caixeiro biajante: Eesiste un percurso de, ne l mássimo, 2000 Km de cumprimiento passando por todas las 15 maiores cidades de la Almanha? La repuosta l'esta detreminada anstáncia de l porblema ye de pouca outelidade pa la resoluçon d'outras anstáncias de l porblema, cumo pedir ua ida i buolta atrabeç de todos ls lugares de Milon cujo cumprimiento total ye ne l mássimo 10 Km. Por esta rezon, la teorie de la cumplexidade aborda porblemas cumputacionales i nun anstáncias particulares de l porblema.
Repersentando anstáncias de porblema
Al cunsidrar porblemas cumputacionales, ua anstáncia de porblema ye ua cadeia subre un alfabeto. Normalmente, l'alfabeto ye cunsidrado cumo sendo l'alfabeto binairo (ó seia, l cunjunto {0,1}), i, assi, las cadeias son bitstrings. Cumo nun cumputador de l mundo rial, oubjetos matemáticos que nun son bitstrings dében ser debidamente codificados. Por eisemplo, númaros anteiros puoden ser repersentados an notaçon binária, i grafos puoden ser codificados diretamente bie sues matrizes d'adjacéncia, ó por codificaçon de sues listas d'adjacéncia an binairo.
Anque alguas probas de cumplexidade-teórica de teoremas regularmente assumir algua scolha cuncreta de codificaçon d'antrada, tenta-se manter la çcusson abstrata l suficiente para ser andependiente de la scolha de la codificaçon. Esto puode ser cunseguido assegurando que defrentes repersentaçones puodan ser trasformadas an outra de forma eficiente.
thumb|200px|Un porblema de decison ten solo dues salidas possibles, si ó nó (ó altarnatibamente 1 ó 0) para qualquiera antrada.
Porblemas de decison cumo lenguaiges formales
Un eisemplo dun porblema de decison ye l seguinte. L'antrada ye un grafo arbitrairo. L porblema cunsiste an decidir se l dado grafo ye conexo ó nó. La lenguaige formal associada l'este porblema de decison ye anton l cunjunto de todos ls grafos conexos—oubbiamente, para oubter ua defeniçon percisa dessa lenguaige, ye perciso decidir cumo grafos son codificados cumo cadeias binárias.
Porblemas de funçon
Un porblema de funçon ye un porblema cumputacional, adonde ua única salida (dua funçon total) ye sperada para cada antrada, mas la salida ye mais cumplexa de l que la dun porblema de decison, esto ye, nun ye solo si ó nó. Eisemplos notables ancluen l porblema de l caixeiro biajante i l porblema de fatoraçon d'anteiros.
Ye tentador pensar que la noçon de porblemas de funçon ye mui mais rica de l que la noçon de porblemas de decison. Inda assi, l causo rialmente nun ye esse, yá que porblemas de funçon puoden ser reformulados cumo porblemas de decison. Por eisemplo, la multiplicaçon de dous númaros anteiros puode ser spressa cumo l cunjunto (la, b, c) tal qual la relaçon la × b = c çcribe. Decidir se ua dada tripla ye nembro deste cunjunto corresponde a resulber l porblema de la multiplicaçon de dous númaros.
Mediçon de l tamanho dua anstáncia
Para medir la deficuldade de resulber un porblema cumputacional, puode-se zeiar ber quanto tiempo l melhor algoritmo necessita para resulber l porblema. Inda assi, l tiempo d'eisecuçon puode, an giral, depender de l'anstáncia. An particular, anstáncias maiores eisigiron mais tiempo para resulber. Assi, l tiempo necessairo para resulber un porblema (ó l spácio necessairo, ó qualquiera outra medida de cumplexidade) ye calculado an funçon de l tamanho de l'anstáncia. Esso giralmente lieba an cunsidraçon l tamanho de l'antrada an bits. La Teorie de la Cumplexidade stá antressada an cumo ls d'algoritmos crecen cun un oumiento ne l tamanho de l'antrada. Por eisemplo, ne l porblema de çcubrir se un grafo ye conetado, quanto tiempo la mais lieba para resulber un porblema para un grafo cun 2m bértices cumparado al tiempo liebado para un grafo cun m bértices?
Se l tamanho de l'antrada ye m, l tiempo gasto puode ser spresso cumo ua funçon de m. Yá que l tiempo gasto an defrentes antradas de mesmo tamanho puode ser defrente, l pior causo an cumplexidade de tiempo T(m) ye defenido cumo sendo l tiempo mássimo dentre todas las antradas de tamanho m. Se T(m) ye un polinómio an m, anton l'algoritmo ye dezido ser un algoritmo de tiempo polinomial. La tese de Cobhan diç qu'un porblema puode ser resolbido cun ua cantidade fatible de recursos se el admite un algoritmo de tiempo polinomial.
Máquina de Turing
thumb|Ua repersentaçon artística dua máquina de Turing
Ua máquina de Turing ye un modelo matemático dua máquina de cumputaçon an giral. Ye un çpositibo teórico que manipula simblos cuntidos nua tira de fita. Máquinas de Turing nun pretenden ser ua tecnologie de cumputaçon na prática, mas si ua spriéncia de pensamiento que repersenta ua máquina de cumputaçon. Acradita-se que se un porblema puode ser resolbido por un algoritmo, anton eisiste ua máquina de Turing que resolbe l porblema. Na berdade, esta ye l'afirmaçon de la tese de Church-Turing. Para alhá desso, sabe-se que todo l que puode ser cumputado an outros modelos de cumputaçon coincido por nós hoije, cumo ua máquina RAM, Jogo de la Bida de Cunway, outómato telemoble ó qualquiera lenguaige de porgramaçon puode ser cumputado nua máquina de Turing. Cumo las máquinas de Turing son fáceles d'analisar matematicamente, i acradita-se que séian tan poderosas quanto qualquiera outro modelo de cumputaçon, la máquina de Turing ye l modelo mais quemumente ousado an teorie de la cumplexidade.
Ua máquina de Turing determinística ye la máquina de Turing de l tipo mais básico, qu'outeliza un cunjunto fixo de regras para detreminar sues açones feturas. Ua máquina de Turing porbabilística ye ua máquina de Turing determinística cun un suprimiento stra de bits aleatórios. La capacidade de tomar decisones porbabilísticas muitas bezes ajuda algoritmos la resolbíren porblemas de forma mais eficiente. Algoritmos que úsan bits aleatórios son chamados algoritmos porbabilísticos. La máquina de Turing nó-determinística ye ua máquina de Turing determinística cun ua caratelística adicional de nó-determenismo, que permite qu'ua máquina de Turing tenga bárias possibles açones feturas a partir dun detreminado stado. Ua maneira d'antender l nó-determenismo ye bisualizar ls galhos de la máquina de Turing cumo ls bários caminos cumputacionales possibles la cada passo, i se eilha resolbe l porblema an qualquiera un desses galhos, diç-se tener resolbido l porblema. Eibidentemente, este modelo nun pretende ser un modelo fesicamente rializable, ye solo ua máquina abstrata teoricamente antressante que dá ourige a classes de cumplexidade particularmente antressantes. Por eisemplo, beija algoritmo nó-determinístico.
Medidas de cumplexidade
Para ua defeniçon percisa de l que senefica resulber un porblema outelizando ua detreminada cantidade de tiempo i spácio, un modelo cumputacional tal cumo la máquina de Turing determinística ye outelizado. L tiempo eisigido por ua máquina de Turing determinística M na antrada x ye l númaro total de trasiçones de stado, ó etapas, que la máquina faç antes de parar i respunder cula salida ("si" ó "nó"). Diç-se que la máquina de Turing M oupera drento de l tiempo f(m), se l tiempo eisigido por M an cada antrada de cumprimiento m ye ne l mássimo f(m). Un porblema de decison La puode ser resolbido an tiempo f(m) se eisiste ua ouparaçon de la máquina de Turing an tiempo f(m) que resolbe l porblema. Cumo la teorie de la cumplexidade stá antressada an classeficar porblemas cun base na sue deficuldade, definen-se cunjuntos de porblemas cun base an alguns critérios. Por eisemplo, l cunjunto de porblemas solucionables ne l tiempo f(m) nua máquina de Turing determinística ye anton andicado por DTIME(f(m)).
Melhor, pior i causo médio de cumplexidade
thumb|250px|Bisualizaçon de l'algoritmo quicksort que ten ne l causo médio zampenho. L melhor, l pior i l causo médio de cumplexidade refíren- se la trés maneiras defrentes de medir la cumplexidade de tiempo (ó qualquiera outra medida de cumplexidade) d'antradas defrentes de l mesmo tamanho. Ua beç qu'alguas antradas de tamanho m puoden ser mais rápidas para resulber de l qu'outras, defenimos las seguintes cumplexidades:
Por eisemplo, cunsidre l'algoritmo d'ourdenaçon quicksort. Esso resolbe l porblema d'ourdenar ua lista d'anteiros que ye dada cumo antrada. L pior causo ye quando l'antrada yá stá ourdenada ó stá an orde ambersa, i l'algoritmo lieba tiempo L(m2) para este causo. Se assumirmos que todas las permutaçones possibles de la lista d'antrada son eigualmente probables, l tiempo médio necessairo pa l'ourdenaçon ye L(m log m). L melhor causo ocorre quando cada pibó debede la lista pula metade, tamien percisando tiempo L(m log m).
Lemites superior i anferior de la cumplexidade de ls porblemas
Para classeficar l tiempo de cumputaçon (ó recursos semelhantes, cumo l cunsumo de spácio), ye necessairo probar ls lemites superiores i anferiores subre la cantidade mínima de tiempo eisigida pul algoritmo mais eficiente para resulber un detreminado porblema. La cumplexidade dun algoritmo ye giralmente antendida cumo la sue cumplexidade de pior causo, a menos que seia specificado l cuntrairo. L'análeze dun detreminado algoritmo cai sob l campo d'análeze d'algoritmos. Para amostrar un lemite superior T(m) subre la cumplexidade de tiempo dun porblema, ye necessairo amostrar solo qu'hai un detreminado algoritmo cun tiempo de funcionamiento, ne l mássimo, T(m). Inda assi, probar lemites anferiores ye mui mais defícel, ua beç que lemites anferiores fázen ua declaraçon subre todos ls possibles algoritmos que resolben un detreminado porblema. La frase "todos ls algoritmos possibles" anclui nun solo ls algoritmos coincidos hoije, mas qualquiera algoritmo que puoda ser çcubierto ne l feturo. Para amostrar un lemite anferior de T(m) para un porblema requer amostrar que nanhun algoritmo puode tener cumplexidade de tiempo menor de l que T(m).
Lemites superiores i anferiores son giralmente andicados usando la notaçon L-grande, que çcunsidera fatores custantes i tenermos menores. Esso faç cun que ls lemites andependan de ls detalhes specíficos de l modelo cumputacional outelizado. Por eisemplo, T(m) = 7m2 + 15m + 40, an notaçon L-grande serie scrito de la seguinte forma T(m) = L(m2).
Defeniçon de classes de cumplexidade
Ye claro, alguas classes de cumplexidade ténen defeniçones cumplexas que nun se ancaixan nesse quadro. Assi, ua classe de cumplexidade típica ten ua defeniçon cumo la seguinte:
Mas lemitar l tiempo de cumputaçon arriba por algua funçon cuncreta f(m) muitas bezes porduç classes de cumplexidade que dependen de l modelo de la máquina scolhida. Por eisemplo, la lenguaige {xx | x ye ua sequéncia binária qualquiera} puode ser resolbida an tiempo linear nua máquina de Turing multi-fitas, mas necessariamente eisige tiempo quadrático ne l modelo de máquinas de Turing single-fita. Se permitirmos bariaçones ne l tiempo polinomial an eisecuçon, la tese de Cobhan-Edmonds afirma que "las cumplexidades de l tiempo an qualesquiera dous modelos razoables i gerales de cumputaçon son polinomialmente relacionados". Esto forma la base pa la classe de cumplexidade P, que ye l cunjunto de porblemas de decison solúbeis por ua máquina de Turing determinística drento de l tiempo polinomial. L cunjunto correspondente de porblemas de funçon ye FP.
Amportantes classes de cumplexidade
300px|thumb|right|Ua repersentaçon de la relaçon antre las classes de cumplexidade Muitas classes de cumplexidade amportantes puoden ser defenidas por lemitando l tiempo ó spácio ousado pul algoritmo. Alguas amportantes classes de cumplexidade de porblemas de decison defenidas desta maneira son las seguintes:
Acuntece que PSPACE = NPSPACE i EXPSPACE = NEXPSPACE pul teorema de Sabitch.
Outras classes de cumplexidade amportantes ancluen BPP, ZPP i RP, que son defenidas usando máquinas de Turing porbabilística; AC i NC, que son defenidas usando circuitos boleanos i BQP i QMA, que son defenidas usando máquinas de Turing quánticas. #P ye ua amportante classe cumplexidade de porblemas de cuntaige (que nun son porblemas de decison). Classes cumo IP i AM son defenidas usando sistemas de proba anteratiba. ALL ye la classe de todos ls porblemas de decison.
Teoremas d'hierarquia
Mais percisamente, l teorema d'hierarquia de tiempo afirma que:
L teorema d'hierarquia de spácio afirma que:
Ls teoremas d'hierarquia de tiempo i de spácio forman la base pa la maiorie de ls resultados de separaçon de classes de cumplexidade. Por eisemplo, l teorema de l'hierarquia de tiempo ne ls diç que P stá stritamente cuntida an EXPTIME, i l teorema hierarquia de l spácio ne ls diç que L stá stritamente cuntida an PSPACE.
Reduçon
Muitas classes de cumplexidade son defenidas usando l cunceito de reduçon. Ua reduçon ye ua trasformaçon dun porblema an outro porblema. Eilha catura la noçon anformal dun porblema que seia pul menos tan defícel quanto outro porblema. Por eisemplo, se un porblema X puode ser resolbido usando un algoritmo para Y, X nun ye mais defícel de l que Y, i dezimos que X se reduç la Y. Eesisten muitos tipos defrentes de reduçon, cun base ne l método de reduçon, cumo reduçones de Cok, reduçones de Karp i reduçones Lebin, i ne l lemite de la cumplexidade de las reduçones, cumo reduçones de tiempo polinomial ó reduçones log-space.
La reduçon mais quemumente ousada ye ua reduçon an tiempo polinomial. Esso senefica que l porcesso de reduçon lieba tiempo polinomial. Por eisemplo, l porblema de l quadrado dun anteiro puode ser reduzido pa l porblema de la multiplicaçon de dous númaros anteiros. Esso senefica qu'un algoritmo para multiplicar dous anteiros puode ser ousado pa l quadrado dun anteiro. De fato, esso puode ser feito dando la mesma antrada para ambas las antradas de l'algoritmo de multiplicaçon. Assi, bemos que l porblema de l quadrado dun anteiro nun ye mais defícel de l que l porblema de la multiplicaçon, yá que l porblema de l quadrado dun anteiro puode ser reduzido al porblema de la multiplicaçon.
Esso motiba l cunceito dun porblema que ser defícel para ua classe de cumplexidade. Un porblema X ye defícel para ua classe de porblemas C se to porblema an C puode ser reduzido la X. Assi, nanhun porblema an C ye mais defícel de l que X, ua beç qu'un algoritmo para X ne ls permite resulber qualquiera porblema an C. Ye claro que la noçon de porblemas defíceles depende de l tipo de reduçon a ser outelizado. Pa las classes de cumplexidade maiores de l que P, reduçones an tiempo polinomial son quemumente ousados. An particular, l cunjunto de porblemas que son defíceles para NP ye l cunjunto de porblemas NP-defícel.
Se un porblema X stá an C i ye defícel para C, anton diç-se que X ye cumpleto para C. Esto senefica que X ye l porblema mais defícel an C. (Ua beç que muitos porblemas poderien ser eigualmente defíceles, puode-se dezir que X ye un de ls ls porblemas mais defíceles an C.) Assi, la classe de porblemas NP-cumpleto cuntén ls porblemas mais defíceles an NP, nesse sentido eilhes son ls mais propensos la nun stáren an P. Cumo l porblema P = NP nun fui resolbido, ser capaç de reduzir un coincido porblema NP-cumpleto, Π2, para outro porblema, Π1, andicarie que nun hai nanhue soluçon coincida an tiempo polinomial para Π1. Esso ocorre porque ua soluçon an tiempo polinomial para Π1 renderie ua soluçon an tiempo polinomial para Π2. De la mesma forma que todos ls porblemas NP puoden ser reduzidos al cunjunto, ancontrar un porblema NP-cumpleto que podisse ser resolbido an tiempo polinomial seneficarie que P = NP.
Amportantes porblemas an abierto
thumb|250px|Diagrama de classes de cumplexidade assumindo que P ≠ NP. L'eisisténcia de porblemas an NP fura tanto de P quanto de NP-cumpleto, neste causo, fui stablecida por Ladner.
Porblemas an NP que nun se sabe se pertencen la P ó la NP-cumpleto
Fui mostrado por Ladner que, se P ≠ NP, anton eisisten porblemas an NP que nun stan nin an P nin an NP-cumpleto. Tales porblemas son chamados de porblemas NP-antermediairo. L porblema de l eisomorfismo de grafos, l porblema de l logaritmo çcreto i l porblema de fatoraçon d'anteiros son eisemplos de porblemas qu'acradita-se que séian NP-antermediairo. Eilhes son alguns de ls mui poucos porblemas NP que nun se sabe se stan an P ó an NP-cumpleto.
L porblema de l'eisomorfismo de grafos ye l porblema cumputacional para detreminar se dous grafos fenitos son eisomorfos. Un amportante porblema nun resolbido na teorie de la cumplexidade ye se l porblema de l'eisomorfismo de grafos stá an P, NP-cumpleto, ó NP-antermediairo. La repuosta nun ye coincida, mas acradita-se que l porblema nun seia, pul menos, NP-cumpleto. Se l'eisomorfismo de grafos fur NP-cumpleto, l'hierarquia de tiempo polinomial colapsa para sou segundo nible. Ua beç qu'acradita-se bemente que l'hierarquia polinomial nun colapse para nanhun nible fenito, acradita-se que l'eisomorfismo de grafos nun seia NP-cumpleto. L melhor algoritmo para este porblema, d'acuordo cun Laszlo Babai i Eugene Luks ten tiempo d'eisecuçon 2L(√(m log(m))) para grafos cun m bértices.
L porblema de la fatoraçon d'anteiros ye l porblema cumputacional para detreminar la fatoraçon prima dun dado anteiro. Formulado cumo un porblema de decison, ye l porblema para decidir se l'antrada ten un fator menor que k. Nanhun algoritmo de fatoraçon d'anteiro eficiente ye coincido, i este fato ye la base de bários sistemas critográficos modernos, cumo l'algoritmo RSA. L porblema de la fatoraçon d'anteiros stá an NP i an co-NP (i até mesmo an UP i co-UP ). Se l porblema ye NP-cumpleto, l'hierarquia de tiempo polinomial colapsará para sou purmeiro nible (ó seia, NP será eigual la co-NP). L melhor algoritmo coincido para fatoraçon d'anteiros ye l GNFS (general number field siebe), que lieba tiempo L(i(64/9) 1/3(m.log 2)1/3(log (m.log 2))2/3 ) para fatorar un anteiro de m-bit. Inda assi, l melhor algoritmo quántico coincido para este porblema, l algoritmo de Shor, ye eisecutado an tiempo polinomial. Anfelizmente, este fato nun diç mui subre adonde stá l porblema cun relaçon a classes de cumplexidade nó-quántica.
Separaçones antre outras classes de cumplexidade
Na mesma linha, co-NP ye la classe que cuntén ls porblemas de l cumplemiento (ó seia, porblemas culas repuostas si / nun ambertidsa) de ls porblemas NP. Acradita-se que NP nun seia eigual la co-NP, inda assi, inda nun fui cumprobado. Ten sido mostrado que, se essas dues classes de cumplexidade nun son eiguales, anton P nun ye eigual la NP.
Suspeita-se que P i BPP séian eiguales. Inda assi, ye un porblema an abierto, ne l momiento, se BPP = NEXP.
L qu'antratabelidade senefica na prática stá abierto an debate. Dezir qu'un porblema nun stá an P nó amplica que todos ls grandes causos de porblemas son defíceles ó até mesmo que la maiorie deilhes son. Por eisemplo, l porblema de la decison na Aritmética de Presburger ten demunstrado nun star an P, inda fúrun escritos algoritmos que resolben l porblema an tiempos razoables na maiorie de ls causos. De la mesma forma, ls algoritmos puoden resulber l porblema de la mochila NP-cumpleto nua ampla faixa de tamanhos an menos que l tiempo quadrático i resolbedores de SAT rotineiramente lidan cun grandes anstáncias de l porblema de sastifatibelidade boleana NP-cumpleto.
Teorie de la cumplexidade cuntínua
La teorie de la cumplexidade cuntínua puode se referir a la teorie de la cumplexidade de ls porblemas qu'ambolben funçones cuntínuas que son aprossimadas por çcretizaçones, cumo studado an análeze numérica. Ua abordaige pa la teorie de la cumplexidade de l'análeze numérica ye la cumplexidade baseada an anformaçon (IBC).
La teorie de la cumplexidade cuntínua tamien puode se referir a la teorie de la cumplexidade de l'uso de la cumputaçon analógica, qu'outeliza sistemas dinámicos cuntinos i eiquaçones defrenciales. La teorie de cuntrole puode ser cunsidrada ua forma de cumputaçon i eiquaçones defrenciales son ousadas na modelaige de sistemas de tiempo cuntino i híbridos de tiempo çcreto-cuntino.
Stória
Antes de la pesquisa propiamente dita splicitamente dedicada a la cumplexidade de ls porblemas algorítmicos ampeçar, ls numerosos fundamientos fúrun stablecidos por bários pesquisadores. L mais anfluente antre estes fui la defeniçon de las máquinas de Turing por Alan Turing an 1936, qu'acabou por ser ua noçon mui robusta i flexible de cumputador.
datan l'ampeço de ls studos sistemáticos an cumplexidade cumputacional cul amportante artigo "On the Cumputational Cumplexity of Algorithms" de Juris Hartmanis i Richard Stearnes (1965), que stableciu las defeniçones de cumplexidade de tiempo i de spácio i probou ls teoremas d'hierarquia.
D'acuordo cun, trabalhos anteriores que studórun porblemas solucionables por máquinas de Turing cun recursos specíficos lemitados anclui la defeniçon de John Myhill de outómatos linearmente lemitados (Myhill 1960), l studo de Raymond Smullyan subre cunjuntos rudimentares (1961), assi cumo l'artigo de Sao Yamada subre cumputaçon an tiempo rial (1962). Un pouco mais cedo, Boris Trakhtenbrot (1956), un pioneiro ne l campo de la URSS, studou outra medida específica de cumplexidade. Cumo lembra el: "Assi i to, [miu] antresse enicial [na teorie de ls outómatos] era cada beç mais puosto de lado an detrimiento a la cumplexidade cumputacional, ua scitante fuson de métodos cumbinatoriales, heirdada de la teorie de la quemutaçon, cul arsenal cunceitual de la teorie d'algoritmos. Essas eideias me ocorrírun antes, an 1955, quando you conhei l termo "funçon de sinalizaçon", qu'hoije ye quemumente coincido cumo "medida de cumplexidade"."
- Boris Trakhtenbrot