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.
Please use this identifier to cite or link to this item:
http://bibdigital.epn.edu.ec/handle/15000/22911| Title: | Complejidad computacional de problemas de distribución justa de recursos desde el punto de vista descriptivo. |
| Authors: | Risco Iturralde, Paúl Alejandro |
| Keywords: | COMPLEJIDAD COMPUTACIONAL ESTRUCTURAS DISCRETAS CIENCIAS DE LA COMPUTACIÓN NP-HARDNESS |
| Issue Date: | Aug-2022 |
| Publisher: | Quito : EPN, 2022. |
| 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. |
| 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. |
| 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. |
| URI: | http://bibdigital.epn.edu.ec/handle/15000/22911 |
| Type: | bachelorThesis |
| Appears in Collections: | Tesis Matemáticas (MAT) |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| CD 12367.pdf | 615,49 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.