sistemas de prueba proposicional y teorías aritméticas acotadas correspondientes
Esta pregunta está inspirada en una pregunta similar sobre las matemáticas aplicadas en el desbordamiento matemático, y ese fastidio pensó que las preguntas importantes de TCS como P vs. NP podrían ser independientes de ZFC (u otros sistemas). Como un poco de historia, la matemática inversa es el...
Esta es una pregunta ingenua, por mi experiencia; disculpas de antemano. La Conjetura de Goldbach y muchas otras preguntas no resueltas en matemáticas se pueden escribir como fórmulas cortas en cálculo de predicados. Por ejemplo, el artículo de Cook "¿Pueden las computadoras descubrir...
La pregunta sobre la teoría " ¿Qué es NP restringido a testigos de tamaño lineal? " Pregunta sobre la clase NP restringida a testigos de tamaño lineal , peroO ( n )O(n)O(n) ¿Existen problemas naturales de NP completo en los que (sí) las instancias de tamaño requieren testigos de tamaño mayor que...
A menudo puede encontrar métodos de plano de corte, propagación variable, ramificación y encuadernación, aprendizaje de cláusulas, retroceso inteligente o incluso heurística humana tejida a mano en solucionadores SAT. Sin embargo, durante décadas, los mejores solucionadores de SAT se han basado en...
Recientemente he visto varios artículos sobre arxiv que se refieren a un sistema de prueba llamado suma de cuadrados. ¿Alguien puede explicar qué es una prueba de suma de cuadrados y por qué esas pruebas son importantes / interesantes? ¿Cómo se relacionan con otros sistemas de prueba algebraica?...
¿Hay alguna encuesta de algoritmos para calcular interpolantes? ¿Qué pasa con los documentos en un solo algoritmo? El caso que más me interesa es y , más la restricción de que el interpolante es lo más pequeño posible. (Conozco el artículo de McMillan de 2005 , que describe cómo obtener...
XORification es la técnica para hacer que una función o fórmula booleana sea más difícil al reemplazar cada variable por el XOR de k ≥ 2 variables distintas x 1 ⊕ ... ⊕ x k . xxxk≥2k≥2k\geq 2x1⊕…⊕xkx1⊕…⊕xkx_1 \oplus \ldots \oplus x_k Soy consciente de los usos de esta técnica en la complejidad de...
Estoy buscando ejemplos naturales de algoritmos eficientes (es decir, en tiempo polinómico) st su corrección y eficiencia pueden demostrarse de manera constructiva (p. ej., en o ), peroPAGR APAGRUNPRAHUNHUNHA no se conoce ninguna prueba que utilice solo conceptos eficientes (es decir, no sabemos...
Al leer el documento " Una teoría aplicativa para FPH " puede encontrar el siguiente pasaje: Considerando las teorías que caracterizan las clases de complejidad computacional, existen tres enfoques diferentes: en uno, las funciones que se pueden definir dentro de la teoría son...
Sabemos que los solucionadores de SAT basados en DPLL no responden correctamente en casos insatisfactorios de (principio del agujero de paloma), por ejemplo, "hay un mapeo inyectivo de n + 1 a n ":P H PPAGHPAG\mathrm{PHP}n + 1norte+1n+1nortenorten P H Pn + 1norte: = ⎛⎝⋀i ∈ [ n + 1 ] ⋁j ∈ [ n...
Esta pregunta trata sobre la lógica proposicional y todos los casos de "resolución" deben leerse como "resolución proposicional". Esta pregunta es algo extremadamente básico, pero me ha estado molestando por un tiempo. Veo personas afirmar que la resolución proposicional está completa, pero...
¿Habría alguna consecuencia importante si SAT tuviera a lo sumo pruebas subexponenciales no firmes o, aún más fuerte, SAT tuviera algoritmos de tiempo
Suponiendo que NP! = CoNP, entonces no hay un certificado de tamaño polinómico para el problema de coNP completo. ¿Pero qué pasa con el certificado de tamaño subexponencial? Particularmente para coSAT, ¿hay una prueba de tamaño subexponencial para demostrar que una fórmula no es satisfactoria? Si...
Recordemos que la anchura de una resolución refutación de una fórmula CNF es el número máximo de literales en cualquier cláusula que ocurre en . Para cada , hay fórmulas insatisfactorias en 3-CNF st cada refutación de resolución de requiere un ancho de al menos .F R w F F...
Recientemente comencé a leer mucho sobre la complejidad de las pruebas y realmente he disfrutado lo que he estado leyendo. Realmente me gustaría aprender más sobre esto, pero estoy teniendo dificultades para encontrar un buen material para principiantes para comenzar. ¿Alguien podría recomendar...
Suponga que NP = co-NP y el polinomio limita la longitud de la prueba de insatisfacción para una instancia de 3-CNF x . Entonces, ¿hay algún resultado sobre qué forma puede tomar cualquier prueba de insatisfacción para x de longitud ≤ p ( x ) ? Es decir, en general, ¿tal prueba tendría que usar,...
La motivación para esta pregunta es el hecho de que la mayoría de las cadenas de n bits son incompresibles. Intuitivamente, podemos proponer por analogía que la mayoría de las pruebas para tautologías son incompresibles para el tamaño polinómico. Básicamente, mi intuición es que algunas pruebas son...
La resolución es un esquema para demostrar la insatisfacción de los CNF. Una prueba en resolución es una deducción lógica de la cláusula vacía para las cláusulas iniciales de la CNF. En particular, se puede inferir cualquier cláusula inicial, y de dos cláusulas A ∨ xA∨xA \lor x y B ∨ ¬ xB∨¬xB \lor...
¿Existe una clase natural de fórmulas de CNF, preferiblemente una que se haya estudiado previamente en la literatura, con las siguientes propiedades:CCC CCC es un caso fácil de SAT, como por ejemplo Horn o 2-CNF, es decir, la membresía en puede probarse en tiempo polinomial, y las fórmulas pueden...
En una charla de Razborov, se publica una pequeña y curiosa declaración. Si FACTORING es difícil, entonces el pequeño teorema de Fermat no es demostrable en S12S21S_{2}^{1} . ¿Qué es S12S21S_{2}^{1} y por qué las pruebas actuales no están en S12S21S_{2}^{1} ?