¿Dónde busco ayuda con la investigación / publicación?

11

He estado desarrollando un algoritmo SAT durante un tiempo y he llegado a un punto en el que me gustaría compartirlo. No conozco a muchas personas en ciencias de la computación, y no estoy seguro exactamente a dónde acudir.

Me pregunto qué recursos están disponibles para alguien con un algoritmo que está considerando publicar. También necesito ayuda para analizar el tiempo de ejecución y la corrección de mi algoritmo.

Mi principal problema es analizar el tiempo de ejecución. Necesito ayuda con un análisis detallado de esto. Estoy bastante seguro de que el algoritmo es correcto, pero sería útil si alguien verificara esto también.

Entonces, ¿hay alguien que esté dispuesto a analizar mi algoritmo? Además, ¿qué recursos están disponibles para una tarea como esta?

Matt Groff
fuente
¿Estás hablando de publicar o verificar tu idea? ¿Qué quiere decir con "recursos"; diarios o medios de verificación?
Raphael
12
Me parece que si el objetivo es publicar, entonces debe haber al menos un análisis de tiempo de ejecución y una idea de "cómo" corregir su algoritmo, suponiendo que sea heurístico. También tendría que comparar lo que hace su algoritmo con el trabajo anterior; sin eso, la publicación es un no-no. De hecho, recomendaría hacerlo primero.
Suresh Venkat
Estoy considerando publicar, pero por ahora estoy realmente buscando ayuda con el análisis. Me doy cuenta de que este sitio puede ayudar con preguntas específicas, pero espero encontrar lugares donde pueda conocer personas que estén dispuestas a ayudar con el análisis. Además, no tengo muchos antecedentes con respecto a otros algoritmos, pero me pregunto si mi enfoque puede ser algo único.
Matt Groff el
Ver también la pregunta relacionada cstheory.stackexchange.com/questions/7600/…
András Salamon

Respuestas:

32

Si su algoritmo SAT está destinado a ser práctico, entonces debe ejecutar los puntos de referencia de la competencia SAT en él. La comunidad de resolución de SAT tomará su trabajo mucho más en serio si puede demostrar que su enfoque es competitivo con los solucionadores existentes. Su solucionador no tiene que ser más rápido que cualquier solucionador, o resolver más casos, pero debe ser un competidor serio. No necesita una máquina muy rápida o potente para ejecutar los puntos de referencia; simplemente puede comparar el tiempo de ejecución con uno de los solucionadores SAT gratuitos como MiniSAT o PicoSAT . Estos solucionadores también le permitirán ver cómo deberían ser las respuestas.

Si está trabajando en un solucionador práctico que utiliza nuevas técnicas, y su enfoque aún no es competitivo, le sugiero que pruebe estos puntos de referencia. Le ayudarán a comprender los tipos de problemas que debe intentar resolver y el tipo de rendimiento al que debe aspirar. Es posible que también desee leer algunos de los capítulos clave del Manual de satisfacción o la encuesta reciente.

  • Nudo Pipatsrisawat y Adnan Darwiche, Sobre solucionadores modernos de satisfacción de la cláusula de aprendizaje , Journal of Automated Reasoning 44 277–301, 2010. ( PDF )

para ver los tipos de argumentos que respaldan a los principales solucionadores. Si tiene nuevas ideas que aún no están optimizadas para desempeñarse tan bien como los mejores solucionadores, deberá explicar las ventajas potenciales de su enfoque a alguien que conozca la larga secuencia de razonamiento teórico que ha llevado al conjunto actual de "mejores practicar "decisiones de diseño".

Si su contribución es puramente teórica, entonces debe conocer los numerosos documentos en esta área y explicar en su documento por qué su enfoque es mejor al menos de alguna manera. Eche un vistazo al trabajo reciente de, por ejemplo, Amin Coja-Oghlan o Alan Frieze para tener una idea del estado del arte y de consejos útiles para documentos importantes.

András Salamon
fuente
Vea también la discusión en cstheory.stackexchange.com/questions/1719/…
András Salamon
Vea también la discusión en cstheory.stackexchange.com/questions/7600/…
András Salamon
2

Como ahora desea compartir su algoritmo, mi sugerencia personal es la siguiente: cree un sitio web muy simple. El sitio debe poner a disposición estas 2 cosas:

  1. El código fuente del algoritmo.
  2. Un documento que describe brevemente su enfoque. ¿Dónde tu enfoque es diferente? ¿Cuál es la nueva idea detrás de esto? Este documento no necesita ser un documento técnico perfectamente escrito, ni debe contener ninguna prueba formal: una presentación en power point sería suficiente para "transmitir" el núcleo de su idea. Simplemente explíquenos por qué cree que su algoritmo es diferente. Quizás sea único, quién sabe.

Giorgio Camerani
fuente
No creo que crear un sitio web sea una muy buena idea. Debido a que muchas personas construyen un sitio web cuando 'piensan' que han resuelto grandes problemas o han encontrado TOE. por ejemplo, dharwadker.org/tevet/isomorphism matpitka.blogspot.com Teorema: "Por cada problema no resuelto hay al menos un tipo que afirma que lo resolvió y crea un sitio web". Mala idea -1 :(
Pratik Deoghare
@TheMachineCharmer: No quise decir algo así. El sitio web era solo una forma de permitir a las personas descargar el código y leer el documento que describe el algoritmo. No quise decir un sitio web de "celebración". En cambio, me refería a un sitio web para simplemente compartir material, sin ningún reclamo "triunfante" (algo similar a lo que dijo en su respuesta, aunque el suyo tiene un sabor algo más "oficial").
Giorgio Camerani
1
  1. Puede escribir sus ideas en formato de papel estándar.
  2. Publícalo en ArXiv .
  3. Compartir código fuente en github .
  4. Dedique un tiempo a aprender el análisis del tiempo de ejecución y actualice su trabajo cuando haya terminado.

Por ejemplo, puede escribir una encuesta y al final sugerir su solución como un nuevo enfoque prometedor. Pero sin pruebas de corrección y análisis de tiempo de ejecución, no mucha gente lo tomará en serio (pero algunos lo harán).

Pratik Deoghare
fuente