About: E (clase de complejidad)

En complejidad computacional, la clase de complejidad E es el conjunto de problemas de decisión que pueden ser resueltos por una Máquina de Turing determinista en tiempo 2O(n), y es por lo tanto igual a la clase de complejidad DTIME(2O(n)). E es menos importante en la complejidad computacional que la clase similar EXPTIME, porque no es cerrada para reducciones en tiempo polinómico.

Property	Value
dbo:abstract	En complejidad computacional, la clase de complejidad E es el conjunto de problemas de decisión que pueden ser resueltos por una Máquina de Turing determinista en tiempo 2O(n), y es por lo tanto igual a la clase de complejidad DTIME(2O(n)). E es menos importante en la complejidad computacional que la clase similar EXPTIME, porque no es cerrada para reducciones en tiempo polinómico. (es) En complejidad computacional, la clase de complejidad E es el conjunto de problemas de decisión que pueden ser resueltos por una Máquina de Turing determinista en tiempo 2O(n), y es por lo tanto igual a la clase de complejidad DTIME(2O(n)). E es menos importante en la complejidad computacional que la clase similar EXPTIME, porque no es cerrada para reducciones en tiempo polinómico. (es)
dbo:wikiPageExternalLink	http://ftp.cs.rutgers.edu/pub/allender/ALRch33.pdf http://eccc.uni-trier.de/report/1994/004/ http://dimacs.rutgers.edu/TechnicalReports/abstracts/1994/94-18.html
dbo:wikiPageID	3718922 (xsd:integer)
dbo:wikiPageLength	2015 (xsd:integer)
dbo:wikiPageRevisionID	119638409 (xsd:integer)
prop-es:apellido	Allender (es) Allender (es)
prop-es:author1Link	Russell Impagliazzo (es) Russell Impagliazzo (es)
prop-es:autor	Loui, Michael C. (es) Regan, Kenneth W. (es) Loui, Michael C. (es) Regan, Kenneth W. (es)
prop-es:contribution	Measure on small complexity classes with applications for BPP (es) Decision versus search problems in super-polynomial time (es) Measure on small complexity classes with applications for BPP (es) Decision versus search problems in super-polynomial time (es)
prop-es:first	M. (es) R. (es) G. (es) E. (es) O. (es) M. (es) R. (es) G. (es) E. (es) O. (es)
prop-es:id	ECCC TR94-004, DIMACS TR 94-18 (es) ECCC TR94-004, DIMACS TR 94-18 (es)
prop-es:issue	4 (xsd:integer) 9 (xsd:integer)
prop-es:journal	dbpedia-es:SIAM_Journal_on_Computing Theoretical Computer Science (es) Journal of Computer and System Sciences (es)
prop-es:last	Watanabe (es) Strauss (es) Book (es) Allender (es) Impagliazzo (es) Tardos (es) Watanabe (es) Strauss (es) Book (es) Allender (es) Impagliazzo (es) Tardos (es)
prop-es:nombre	Eric (es) Eric (es)
prop-es:pages	213 (xsd:integer) 222 (xsd:integer) 249 (xsd:integer) 281 (xsd:integer) 807 (xsd:integer)
prop-es:title	dbpedia-es:Symposium_on_Foundations_of_Computer_Science Comparing complexity classes (es) Comparison of polynomial time completeness notions (es) On languages accepted in polynomial time (es)
prop-es:título	Complexity Classes (es) Complexity Classes (es)
prop-es:url	http://ftp.cs.rutgers.edu/pub/allender/ALRch33.pdf
prop-es:volume	1 (xsd:integer) 3 (xsd:integer) 53 (xsd:integer)
prop-es:year	1972 (xsd:integer) 1974 (xsd:integer) 1987 (xsd:integer) 1989 (xsd:integer) 1994 (xsd:integer)
dct:subject	category-es:Clases_de_complejidad
rdfs:comment	En complejidad computacional, la clase de complejidad E es el conjunto de problemas de decisión que pueden ser resueltos por una Máquina de Turing determinista en tiempo 2O(n), y es por lo tanto igual a la clase de complejidad DTIME(2O(n)). E es menos importante en la complejidad computacional que la clase similar EXPTIME, porque no es cerrada para reducciones en tiempo polinómico. (es) En complejidad computacional, la clase de complejidad E es el conjunto de problemas de decisión que pueden ser resueltos por una Máquina de Turing determinista en tiempo 2O(n), y es por lo tanto igual a la clase de complejidad DTIME(2O(n)). E es menos importante en la complejidad computacional que la clase similar EXPTIME, porque no es cerrada para reducciones en tiempo polinómico. (es)
rdfs:label	E (clase de complejidad) (es) E (clase de complejidad) (es)
owl:sameAs	freebase:E (clase de complejidad)
prov:wasDerivedFrom	wikipedia-es:E_(clase_de_complejidad)?oldid=119638409&ns=0
foaf:isPrimaryTopicOf	wikipedia-es:E_(clase_de_complejidad)
is owl:sameAs of	dbr:E (clase de complejidad)
is foaf:primaryTopic of	wikipedia-es:E_(clase_de_complejidad)