Contributions to the study of resource-bounded measure

• Autores: Elvira Mayordomo
• Directores de la Tesis: José Luis Balcázar Navarro (dir. tes.)
• Lectura: En la Universitat Politècnica de Catalunya (UPC) ( España ) en 1994
• Idioma: inglés
• Tribunal Calificador de la Tesis: Jacobo Toran Romero (presid.) , Ricard Gavaldà Mestre (secret.) , V. Book Ronald (voc.) , Mario Rodríguez Artalejo (voc.) , Marta Sanz (voc.)
• Texto completo no disponible (Saber más ...)
• 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.