Onde solicito ajuda com pesquisa / publicação?

11

Estou desenvolvendo um algoritmo SAT há algum tempo e cheguei a um ponto em que gostaria de compartilhá-lo. Não conheço muitas pessoas em ciência da computação e não sei exatamente para onde me virar.

Eu estou querendo saber quais recursos estão disponíveis para alguém com um algoritmo que está pensando em publicar. Também preciso de ajuda para analisar o tempo de execução e a correção do meu algoritmo.

Meu principal problema está na análise do tempo de execução. Preciso de ajuda com uma análise detalhada disso. Estou bastante certo de que o algoritmo está correto, mas seria útil se alguém verificar isso também.

Então, há alguém que estaria disposto a analisar meu algoritmo? Além disso, quais recursos estão disponíveis para uma tarefa como essa?

Matt Groff
fonte
Você está falando sobre publicar ou verificar sua ideia? O que você quer dizer com "recursos"; revistas ou meios de verificação?
Raphael
12
Parece-me que, se a publicação é o objetivo, é preciso ter pelo menos uma análise em tempo de execução e uma sensação de "como" o seu algoritmo está correto, supondo que seja uma heurística. Você também teria que comparar o que seu algoritmo faz com trabalhos anteriores - sem isso, a publicação é um não-não. Na verdade, eu recomendaria fazer isso primeiro.
Suresh Venkat
Estou pensando em publicar, mas, por enquanto, estou realmente procurando ajuda com a análise. Sei que este site pode ajudar com perguntas específicas, mas espero encontrar lugares onde possa conhecer pessoas que estejam dispostas a ajudar na análise. Além disso, não tenho muitos conhecimentos sobre outros algoritmos, mas me pergunto se minha abordagem pode ser um pouco única.
Matt Groff
Consulte também a pergunta relacionada cstheory.stackexchange.com/questions/7600/…
András Salamon

Respostas:

32

Se o seu algoritmo SAT for prático, você deve executar os benchmarks de competição do SAT . A comunidade de solução SAT levará seu trabalho muito mais a sério se você puder mostrar que sua abordagem é competitiva com os solucionadores existentes. Seu solucionador não precisa ser mais rápido que qualquer solucionador ou resolver mais instâncias, mas deve ser um concorrente sério. Você não precisa de uma máquina muito rápida ou poderosa para executar os benchmarks; você pode simplesmente comparar o tempo de execução com um dos resolvedores SAT gratuitos, como o MiniSAT ou o PicoSAT . Esses solucionadores também permitem que você veja como devem ser as respostas.

Se você estiver trabalhando em um solucionador prático que use novas técnicas e sua abordagem ainda não for competitiva, eu ainda sugeriria tentar esses benchmarks. Eles o ajudariam a entender os tipos de problemas que você deveria ter como objetivo resolver e o tipo de desempenho que deveria procurar. Você também pode ler alguns dos capítulos principais do Manual de Satisfação ou a pesquisa recente

  • Knot Pipatsrisawat e Adnan Darwiche, Sobre os solventes modernos de satisfação com cláusulas de aprendizagem , Journal of Automated Reasoning 44 277–301, 2010. ( PDF )

para ver os tipos de argumentos que apóiam os principais solucionadores. Se você tiver novas idéias que ainda não estão otimizadas para o desempenho e os principais solucionadores, precisará explicar as vantagens potenciais de sua abordagem para alguém que conheça a longa sequência de raciocínio teórico que levou ao conjunto atual de "melhores praticar "decisões de design.

Se sua contribuição é puramente teórica, você precisa estar ciente dos muitos trabalhos nessa área e explicar em seu trabalho por que sua abordagem é melhor, pelo menos de alguma maneira. Veja os trabalhos recentes de Amin Coja-Oghlan ou Alan Frieze, para ter uma idéia do estado da arte e dicas úteis para artigos importantes.

András Salamon
fonte
Veja também a discussão em cstheory.stackexchange.com/questions/1719/…
András Salamon
Veja também a discussão em cstheory.stackexchange.com/questions/7600/…
András Salamon
2

Como agora você deseja compartilhar seu algoritmo, minha sugestão pessoal é a seguinte: crie um site muito simples. O site deve disponibilizar estas duas coisas:

  1. O código fonte do algoritmo.
  2. Um documento descrevendo brevemente sua abordagem. Onde sua abordagem é diferente? Qual é a nova idéia por trás disso? Este documento não precisa ser um documento técnico perfeitamente escrito, nem precisa conter nenhuma prova formal: uma apresentação em power point seria suficiente para "transmitir" o núcleo da sua idéia. Apenas explique-nos por que você acha que seu algoritmo é diferente. Talvez seja único, quem sabe.

Giorgio Camerani
fonte
Não acho que criar um site seja uma boa ideia. Como muitas pessoas constroem um site quando 'pensam', resolveram grandes problemas ou encontraram o TOE. Por exemplo, dharwadker.org/tevet/isomorphism matpitka.blogspot.com Teorema: "Para todo problema não resolvido, há pelo menos um indivíduo que afirma que o resolveu e cria um site". Bad idea -1 :(
Pratik Deoghare
@TheMachineCharmer: Eu não quis dizer algo assim. O site era apenas uma maneira de permitir que as pessoas baixassem o código e lessem o documento que descreve o algoritmo. Não quis dizer um site de "comemoração". Em vez disso, pretendia que um site compartilhasse apenas material, sem nenhuma reivindicação "triunfante" (algo semelhante ao que você disse em sua resposta, embora o seu tenha um sabor um pouco mais "oficial").
Giorgio camerani
1
  1. Você pode escrever suas idéias em formato de papel padrão.
  2. Publique-o no ArXiv .
  3. Compartilhe o código fonte no github .
  4. Passe algum tempo aprendendo a análise do tempo de execução e atualize seu trabalho quando terminar.

Por exemplo, você pode escrever um documento de pesquisa e, no final, sugerir sua solução como nova abordagem promissora. Mas, sem prova de correção e análise do tempo de execução, muitas pessoas não levarão isso a sério (mas algumas o farão).

Pratik Deoghare
fonte