completitud

completitud

 
f. lóg. Propiedad de un sistema lógico por la que cualquier expresión cerrada es derivable o refutable dentro del mismo sistema.
Ejemplos ?
El espacio Q p de todos los números p -ádicos tiene la propiedad topológica, deseable, de completitud, que nos permite el desarrollo del Análisis p-ádico, similar al Análisis real.
Gödel demostró que no se podía demostrar la completitud de ningún sistema formal no contradictorio que fuera suficientemente amplio para incluir al menos la aritmética, sólo mediante sus propios axiomas.
Por lo tanto si ambas definiciones de la NP-completitud son iguales hay un problema co-NP-completo (bajo ambas definiciones) como por ejemplo el complementario del problema de la satisfacibilidad booleana que es también NP-completo (bajo ambas definiciones).
Esto implica que NP co-NP es una pregunta abierta se considera muy poco probable porque también es muy poco probable que las dos definiciones de NP-completitud sean equivalentes.
El teorema fue demostrado por primera vez por Kurt Gödel como una consecuencia del teorema de completitud, pero con el tiempo se han encontrado varias demostraciones adicionales.
El teorema de completitud de Gödel, demostrado por Kurt Gödel en 1929, establece que existen sistemas de primer orden en los que todas las fórmulas lógicamente válidas son demostrables.
Un ejemplo de axiomas y reglas de inferencia que permiten demostrar completitud son los que se dieron más arriba en este artículo.
Algunos de los más famosos son: Problema de satisfacibilidad booleana (SAT) Problema de la mochila (knapsack) Problema del ciclo hamiltoniano Problema del vendedor viajero Problema de la clique Véase también: A la derecha, un diagrama de algunos de los problemas y sus reducciones típicamente usadas para demostrar su completitud NP.
El cuerpo Q p de los números p -ádicos se pueden definir entonces como la completitud del espacio métrico (Q, d p); sus elementos son las clases de equivalencia de sucesiones de Cauchy.
Otro tipo de reducción es empleado frecuentemente para definir NP-completitud es la de reducción de espacio logarítmico many-one que puede ser computerizada empleando únicamente una cantidad logarítmica de espacio.
Centrándose en este aspecto, generalmente referido como completitud de órdenes, se obtiene: Posets acotados, es decir posets con menor y mayor elementos (que son precisamente supremo e ínfimo del conjunto vacío), reticulados, en que cada conjunto finito no vacío tiene supremo e ínfimo, reticulados completos, donde cada conjunto tiene supremo e ínfimo, y órdenes parciales dirigidos completos (dcpos), que garantizan la existencia de supremo en todo subconjunto dirigido y son estudiados en teoría de dominios.
Sin embargo, el teorema de completitud no dice nada al respecto de la demostración de la completitud de la matemática mediante un sistema formal diferente.