Hola,
¿eres nuevo aquí?

Registrate y conecta tu empresa con financiación pública, partners y proyectos.

PID2019-109137GB-C22

Financiado

SISTEMAS DE PRUEBA MAS ALLA DE RESOLUCION: ANALISIS TEORICO

EL PROBLEMA DE LA SATISFACCION DE RESTRICCIONES (CSP) Y SUS DIFERENTES VARIANTES PROPORCIONA UN MARCO TEORICO QUE PERMITE EXPRESAR UNA VASTA FAMILIA DE PROBLEMAS COMPUTACIONALES, TRAS VARIAS DECADAS DE ESFUERZO SE HA DETERMINADO L... ver más

01/01/2019

UPF

37K€

Presupuesto del proyecto: 37K€

Líder del proyecto

UNIVERSITAT POMPEU FABRA No se ha especificado una descripción o un objeto social para esta compañía.

Total investigadores 321

Ver Participantes

Financiación concedida El organismo AGENCIA ESTATAL DE INVESTIGACIÓN notifico la concesión del proyecto el día 2019-01-01

0% 100%

Participantes

UPF

Lider

Proyectos interesantes

CoCoSym Symmetry in Computational Complexity 1M€ Cerrado

CONJEXITY Investigating the Conjectures of Fine-Grained Complexity 1M€ Cerrado

TIN2010-20967-C04-03 TEORIA, APLICACIONES Y SINERGIA EN SAT, CSP Y FDL 77K€ Cerrado

EPRICOT Efficient Proofs and Computation A Unified Algebraic Appro... 2M€ Cerrado

NEAT Non-linear Existential Arithmetic Theories 181K€ Cerrado

EXCICO Extremal Combinatorics and Circuit Complexity 180K€ Cerrado

Últimas noticias

27-11-2024: Videojuegos y creaci... Se abre la línea de ayuda pública: Ayudas para la promoción del sector del videojuego, del pódcast y otras formas de creación digital

27-11-2024: DGIPYME En las últimas 48 horas el Organismo DGIPYME ha otorgado 1 concesiones

27-11-2024: FUNDACION-EOI En las últimas 48 horas el Organismo FUNDACION EOI ha otorgado 2 concesiones

Líder del proyecto

UNIVERSITAT POMPEU FABRA

Total investigadores 321

Presupuesto del proyecto 37K€

Descripción del proyecto EL PROBLEMA DE LA SATISFACCION DE RESTRICCIONES (CSP) Y SUS DIFERENTES VARIANTES PROPORCIONA UN MARCO TEORICO QUE PERMITE EXPRESAR UNA VASTA FAMILIA DE PROBLEMAS COMPUTACIONALES, TRAS VARIAS DECADAS DE ESFUERZO SE HA DETERMINADO LA COMPLEJIDAD COMPUTACIONAL DE MUCHOS CSPS (CONDICIONADO, NATURALMENTE, A SUPOSICIONES ESTANDAR TALES COMO P DIFERENTE DE NP), UN EJEMPLO PARTICULARMENTE EXITOSO DE ESTA LINEA DE INVESTIGACION LO CONSTITUYEN LOS DENOMINADOS CSPS NO-UNIFORMES, CUYO ESTUDIO INICIARON FEDER Y VARDI EN 1998 Y FUE COMPLETADO EN 2017 POR ZHUZ Y BULATOV, SIN EMBARGO, LA COMPLEJIDAD ALGORITMICA DE MUCHOS CSPS DE INTERES ESTA TODAVIA ABIERTA, EN EL TRANSCURSO DE ESTE PROYECTO TODAVIA POR FINALIZAR SE HAN DESARROLLADO ALGUNOS PRINCIPIOS ALGORITMICOS MUY GENERALES BASADOS EN LA FORMULACION DE RELAJACIONES (LINEALES O SEMIDEFINIDAS) DEL PROBLEMA, TALES FAMILIAS DE RELAJACIONES, QUE INCLUYEN LAS JERARQUIAS DE LOVASZ-SCHRIJVER, SHERALI-ADAMS Y LASSERRE, SE ASOCIAN DE MANERA NATURAL A SISTEMAS DE PRUEBA, QUE DADA UNA INSTANCIA INSATISFACIBLE DEL CSP, PRODUCEN UN CERTIFICADO (O PRUEBA) DE LA NO EXISTENCIA DE SOLUCION, LOS SISTEMAS DE PRUEBA QUE SE OBTIENEN DE ESTE MODO SON TAN GENERALES QUE, EN MUCHOS DOMINIOS CONCRETOS SUBSUMEN TODOS LOS ALGORITMOS PARA EL PROBLEMA, ES DECIR, TODO PROBLEMA QUE NO PUEDE SER RESUELTO POR ALGUNO DE ESTOS METODOS NO PUEDE SER RESUELTO EN ABSOLUTO, DE HECHO, ES CONCEBIBLE QUE MUCHOS DE LOS PROBLEMAS DE INTERES QUE TODAVIA ESTAN ABIERTOS ESTEN AL ALCANCE DE ESTOS METODOS AUNQUE, DEBIDO A QUE TODAVIA NO SE HA DELINEADO MUY BIEN SU CAPACIDAD, TODAVIA NO SABEMOS COMO RESOLVERLOS, UNO DE LOS PRINCIPALES OBJETIVOS DE ESTA SOLICITUD ES AUMENTAR EL CONOCIMIENTO DE ESTOS SISTEMAS DE DEMOSTRACION CON EL OBJETIVO DE CARACTERIZAR MEJOR SU ALCANCE (Y SUS LIMITACIONES),PARA ELLO, PRETENDEMOS EXTENDER EL ESTUDIO DE SISTEMAS DE PRUEBA YA CONOCIDOS A NUEVOS CSPS, TALES COMO LA FAMILIA DE LOS DENOMINADOS CSP PROMESA (PROMISE CSP) INTRODUCIDOS RECIENTEMENTE POR BRAKENSIEK AND GURUSWAMI, ESTA FAMILIA DE CSPS HAN GENERADO UNA CONSIDERABLE ACTIVIDAD RECIENTEMENTE Y CONSTITUYEN UNO DE LOS PASOS MAS NATURALES (UNA VEZ LOS CSPS NO-UNIFORMES HAN SIDO COMPLETAMENTE CLASIFICADOS) PARA PROGRESAR EN EL DENOMINADO ENFOQUE ALGEBRAICO EN EL ESTUDIO DE PROBLEMAS COMPUTACIONALES, EN SEGUNDO LUGAR, PRETENDEMOS INVESTIGAR NUEVAS VARIANTES DE SISTEMAS DE PRUEBA YA EXISTENTES A LO LARGO DE DOS EJES DIFERENTES, POR UN LADO, ESTUDIAREMOS NUEVAS VARIANTES DE LAS JERARQUIAS DE LOVASZ-SCHRIJVER, SHERALI-ADAMS Y LASSERRE QUE (PRESUMIBLEMENTE) AMPLIAN SU ALCANCE, POR EL OTRO LADO, ANALIZAREMOS TEORICAMENTE NUEVAS VARIANTES DE ALGUNOS SISTEMAS DE PRUEBA -EN ESTE CASO, RESOLUCION EXTENDIDA (EXTENDED RESOLUTION) Y PROPAGACION DE REDUNDANCIA (PROPAGATION REDUNDANCY)- DESDE UNA PERSPECTIVA DIFERENTE MOTIVADA, EN ESTE CASO, POR ASPECTOS PRACTICOS EN LA RESOLUCION DE PROBLEMAS DE CSP/SAT, EN PARTICULAR, ESTA DIRECCION SE ENMARCA EN EL OBJETIVO -COORDINADO POR EL SUBPROYECTO 1- CONSISTENTE EN IDENTIFICAR FRAGMENTOS DE LOS SISTEMA DE PRUEBA ANTERIORES QUE SEAN MAS POTENTES (INCLUSO AUNQUE SOLO MARGINALMENTE) QUE RESOLUCION -EL SISTEMA SOBRE EL QUE IMPLICITAMENTE PIVOTAN LOS PROGRAMAS BASADOS EN CDCL (CONFLICT-DRIVEN CLAUSE-LEARNING) PERO AL MISMO TIEMPO POSEAN ALGUNAS DE LAS CARACTERISTICAS DE RESOLUCION DE FORMA QUE PUEDAN SER CANDIDATOS PARA REEMPLAZAR A RESOLUCION COMO SISTEMA DE DEMOSTRACION DENTRO DE UN SOLUCIONADOR DE SAT, CONSTRAINT SATISFACTION\PROPOSITIONAL LOGIC\PROOF SYSTEMS\PROOF COMPLEXITY

Conecta tu I+D

Entra hoy

Financiación

Empresas

CTIs/Universidades

Proyectos

Investigadores