BIBDIGITAL
El Repositorio Digital Institucional de la Escuela Politécnica Nacional, ofrece acceso abierto al texto completo de la producción científica de los miembros de la comunidad politécnica. El objetivo del Repositorio, es constituirse como el registro permanente de consulta académica, maximizando su visibilidad, accesibilidad e impacto.
Por favor, use este identificador para citar o enlazar este ítem:
http://bibdigital.epn.edu.ec/handle/15000/22911| Título: | Complejidad computacional de problemas de distribución justa de recursos desde el punto de vista descriptivo. |
| Autor: | Risco Iturralde, Paúl Alejandro |
| Palabras clave: | COMPLEJIDAD COMPUTACIONAL ESTRUCTURAS DISCRETAS CIENCIAS DE LA COMPUTACIÓN NP-HARDNESS |
| Fecha de publicación: | ago-2022 |
| Editorial: | Quito : EPN, 2022. |
| Citación: | 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. |
| Resumen: | 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. |
| Descripción: | 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. |
| URI: | http://bibdigital.epn.edu.ec/handle/15000/22911 |
| Tipo: | bachelorThesis |
| 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 |
Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.