Complejidad computacional de problemas de distribución justa de recursos desde el punto de vista descriptivo.

Risco Iturralde, Paúl Alejandro

Por favor, use este identificador para citar o enlazar este ítem: http://bibdigital.epn.edu.ec/handle/15000/22911

Registro completo de metadatos

Campo DC	Valor	Lengua/Idioma
dc.contributor.author	Risco Iturralde, Paúl Alejandro	-
dc.date.accessioned	2022-09-16T12:47:25Z	-
dc.date.available	2022-09-16T12:47:25Z	-
dc.date.issued	2022-08	-
dc.identifier.citation	Risco Iturralde, P.A.(2022). Complejidad computacional de problemas de distribución justa de recursos desde el punto de vista descriptivo. 123 páginas. Quito : EPN.	es_ES
dc.identifier.other	T-FCM 0329/CD 12367	-
dc.identifier.uri	http://bibdigital.epn.edu.ec/handle/15000/22911	-
dc.description	En la teoría descriptiva de la complejidad computacional, las proyecciones de primer orden son un tipo de reducción muy débil entre problemas de decisión. En este trabajo de fin de carrera se prueba NP-hardness, vía proyecciones de primer orden, de tres problemas de distribución justa analizados en el artículo “Efficiency and Envy-freeness in Fair Division of Indivisible Goods: Logical Representation and Complexity”, de Bouveret y Lang. En uno de los casos el resultado se obtiene a partir de una generalización del concepto de superfluidad encontrado en el artículo “Universal First-Order Logic is Superfluous for NL, P, NP and coNP”, de Borges y Bonet.	es_ES
dc.description.abstract	In the context of descriptive computational complexity, first-order projections are many-one reductions that possess very little computational power. In this undergraduate project, three fair division problems found in Bouveret and Lang’s “Efficiency and Envy-freeness in Fair Division of Indivisible Goods: Logical Representation and Complexity” are proved NP-hard via first-order projections. To get one of the results, a generalization of the concept of superfluity found in Borges and Bonet’s “Universal First-Order Logic is Superfluous for NL, P, NP and coNP” is used.	es_ES
dc.description.sponsorship	Borges Viloria, Nerio Alberto, director.	es_ES
dc.language.iso	spa	es_ES
dc.publisher	Quito : EPN, 2022.	es_ES
dc.rights	openAccess	es_ES
dc.subject	COMPLEJIDAD COMPUTACIONAL	es_ES
dc.subject	ESTRUCTURAS DISCRETAS	es_ES
dc.subject	CIENCIAS DE LA COMPUTACIÓN	es_ES
dc.subject	NP-HARDNESS	es_ES
dc.title	Complejidad computacional de problemas de distribución justa de recursos desde el punto de vista descriptivo.	es_ES
dc.type	bachelorThesis	es_ES
Aparece en las colecciones:	Tesis Matemáticas (MAT)

Ficheros en este ítem:

Fichero	Descripción	Tamaño	Formato
CD 12367.pdf		615,49 kB	Adobe PDF	Visualizar/Abrir

Muestra el registro sencillo del ítem

BIBDIGITAL