Si bien aprecio un intento, esto no está claro y, por todo lo que se da, no está completo. Trataré de darle algunos comentarios críticos basados en lo que he leído.
Primero, necesitas definir tus términos. El bosquejo de su “bosquejo” (no me atrevería a llamar a esto una prueba en absoluto) es vago, poco claro y hace muchas suposiciones.
Primero, ¿dónde está la prueba de corrección ?
Segundo, ¿dónde está el análisis real del peor de los casos ?
- ¿Cómo puede un trabajador de cuello azul usar álgebra en su vida cotidiana?
- ¿Cuáles son las ventajas / desventajas de tomar un curso de Álgebra / Análisis para Informática?
- Cómo obtener X en términos de Y en la expresión x + 1 / x = y
- Si las ecuaciones [matemáticas] x ^ 2 + bx + c = 0 [/ matemáticas] y [matemáticas] bx ^ 2 + cx + 1 = 0 [/ matemáticas] tienen una raíz común, entonces ¿cómo se puede demostrar que [matemáticas ] b + c + 1 = 0 [/ matemáticas]?
- Cómo llamar a la idea errónea matemática de que las operaciones cambian los números, en lugar de que las operaciones sean sinónimo de su resultado
Las ideas onduladas a mano no son una solución. Todo lo que veo es que alguien aplica su idea a UNA instancia. Su explicación tiene que ser precisa, clara y rigurosa matemática. Algunos comentarios que puedo darle para ayudarlo son los siguientes:
-Solo porque converge a un valor no implica que sea correcto. Es literalmente como si te dijera que si haces la fórmula bien formada el tiempo suficiente para que tenga una determinada propiedad. Posiblemente podría hacerlo con una reducción, pero debe ser preciso. Estamos hablando de un problema discreto, debe describir cómo convierte esto en una tarea real. Esa es una falla de computarlo de la manera que estás sugiriendo. Deberá vincular el número de iteraciones que necesita para cualquier instancia si efectivamente converge, y si no, deberá proporcionar una forma de convertirlo en una solución factible. Incluso puede necesitar ambos.
-También no he visto nada aquí que indique que estás proporcionando un algoritmo de aproximación. Tenga en cuenta que los algoritmos de aproximación son tipos de algoritmos muy precisos que tienen propiedades muy particulares.
-Tiene aleatorización en este algoritmo (o lo que creo que es un algoritmo de lo que he leído), tendrá que lidiar con la aleatoriedad y cómo realmente lo establecería como un algoritmo determinista real. Los algoritmos se formulan como procedimientos paso a paso que se garantiza que terminen (en el sentido de que lo necesitamos aquí), y en este caso necesitamos que sea siempre correcto. A menos que vaya a explicar cómo puede utilizar las probabilidades para formular un algoritmo determinista de tiempo polinómico. Un ejemplo de cómo hacer esto es utilizar la desrandomización (ver Algoritmo aleatorio), pero eso es usar probabilidades condicionales.
-Además, debe demostrar que un algoritmo puede resolver “estas ecuaciones” en tiempo polinómico con respecto al tamaño de entrada . No está claro en absoluto este es el caso.
-No puede ser “una muy buena aproximación”, tiene que ser correcta todo el tiempo . De lo contrario, no ha demostrado que 3-SAT sea solucionable en tiempo polinómico. Se usa un algoritmo para resolver un problema. Toma una instancia como entrada y produce salida. Si la salida es correcta para todas las instancias de entrada, decimos que es correcta, pero esto es algo que debe probar ya que simplemente no puede verificar todas las instancias (ya que 3-SAT tiene infinitas instancias).
-Estás haciendo un reclamo serio, no seas perezoso.
Pido disculpas por la abrasividad, pero esto no es una prueba ni está claro. Solo sugiero considerar algunas de las cosas que he mencionado anteriormente, y si todavía está pensando, funciona escribirlo de manera más clara y precisa. Si considera las cosas anteriores, estoy seguro de que su redacción será mucho mejor y más fácil de verificar.
¡Que tengas un hermoso día!
Daniel