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 ), pero
- no se conoce ninguna prueba que utilice solo conceptos eficientes (es decir, no sabemos cómo demostrar su corrección y eficiencia en o ).S 1 2
Puedo hacer ejemplos artificiales yo mismo. Sin embargo, quiero ejemplos naturales interesantes, es decir, algoritmos estudiados por sí mismos, no creados solo para responder a este tipo de preguntas.
Respuestas:
Esta es la misma idea que la respuesta de Andrej pero con más detalles.
Krajicek y Pudlak [ LNCS 960, 1995, pp. 210-220 ] han demostrado que si es una propiedad Σ b 1 que define primos en el modelo estándar y S 1 2 ⊢ ¬ P ( x ) → ( ∃ y 1 , y 2 ) ( 1 < y 1 , y 2 < x ∧ x = y 1 y 2 )PAG( x ) Σsi1
fuente
Otra clase de ejemplos está dada por las pruebas de irreductibilidad y los algoritmos de factorización para polinomios (principalmente sobre campos finitos y sobre los racionales). Estos dependen invariablemente del pequeño teorema de Fermat o de sus generalizaciones (entre otras), y como tales no se sabe que son formalizables en una teoría apropiada de la aritmética limitada. Por lo general, estos algoritmos son aleatorios, pero para ejemplos de tiempo polinomial determinista, uno puede tomar la prueba de irreductibilidad de Rabin o el algoritmo de raíz cuadrada Tonelli-Shanks (formulado para que se requiera un no residuo cuadrático como parte de la entrada).
fuente
La prueba de primalidad de AKS parece un buen candidato si se cree en Wikipedia.
Sin embargo, esperaría que tal ejemplo fuera difícil de encontrar. Las pruebas existentes se redactarán de modo que obviamente no se realicen en aritmética acotada, pero probablemente serán "adaptables" a la aritmética acotada con más o menos esfuerzo (generalmente más).
fuente