Contributions to the study of resource-bounded measure

Resumen

LA TESIS PRESENTA EXTENSIONES Y NUEVAS APLICACIONES DE LA TEORIA DE LA MEDIDA CON RECURSOS ACOTADOS INTRODUCIDA POR JACK LUTZ, ESTA TEORIA REDEFINE CONCEPTOS CLASICOS DE MEDIDA Y CATEGORIA Y LOS REFORMULA DE MANERA QUE PUEDAN APLICARSE A CLASES DE COMPLEJIDAD DE PROBLEMAS COMPUTACIONALES. EN EL CAPITULO 2, SE EXTIENDEN LAS DEFINICIONES DE LUTZ Y SE OBTIENE UNA NOCION VALIDA DE MEDIDA DENTRO DE LA CLASE DE PROBLEMAS RESOLUBLES EN ESPACIO POLINOMICO (LA DEFINICION DE LUTZ SOLO TENIA SENTIDO PARA CLASES EN TIEMPO EXPONENCIAL O MAYORES). CON ESTA DEFINICION, SE DEMUESTRA QUE LOS CONJUNTOS AUTO-REDUCIBLES SON UN CONJUNTO DE MEDIDA O EN ESPACIO POLINOMICO. EN EL CAPITULO 3, SE APLICAN TECNICAS SIMILARES PARA DEMOSTRAR QUE LOS CONJUNTOS BI-INMUNES TIENEN MEDIDA 1 EN TIEMPO EXPONENCIAL, EXTENDIENDO RESULTADOS ANTERIORES PURAMENTE EXISTENCIALES. EN EL CAPITULO 4 SE UTILIZA EL CONCEPTO DE MEDIDA Y ESTOCASTICIDAD DEBIL PARA DEMOSTRAR QUE TODO CONJUNTO "HARD" PARA TIEMPO EXPONENCIAL BAJO UN TIPO ESPECIFICO DE REDUCIBILIDAD ES DENSO; EL RESULTADO OBTENIDO ES EL MAS FUERTE CONOCIDO EN LA ACTUALIDAD. EL CAPITULO 5 ESTUDIA LAS CONSECUENCIAS DE LA HIPOTESIS QUE LA CLASE NP NO TIENE MEDIDA O EN TIEMPO EXPONENCIAL, DERIVANDO NUMEROSAS CONSECUENCIAS ESTRUCTURALES. FINALMENTE, EL CAPITULO 6 RELACIONA NOCIONES COMO LA " -RANDOMNESS" CON LA TEORIA DE LA MEDIDA.