Wohin wende ich mich bei der Recherche / Veröffentlichung?

11

Ich habe eine Weile einen SAT-Algorithmus entwickelt und einen Punkt erreicht, an dem ich ihn gerne teilen möchte. Ich kenne nicht viele Leute in der Informatik und bin mir nicht sicher, wohin ich mich wenden soll.

Ich frage mich, welche Ressourcen für jemanden mit einem Algorithmus verfügbar sind, der eine Veröffentlichung in Betracht zieht. Ich brauche auch Hilfe bei der Analyse der Laufzeit und Korrektheit meines Algorithmus.

Mein Hauptproblem ist die Analyse der Laufzeit. Ich brauche Hilfe bei einer detaillierten Analyse. Ich bin mir ziemlich sicher, dass der Algorithmus korrekt ist, aber es wäre hilfreich, wenn jemand dies ebenfalls überprüfen würde.

Gibt es also jemanden, der bereit wäre, meinen Algorithmus zu analysieren? Welche Ressourcen stehen für eine solche Aufgabe zur Verfügung?

Matt Groff
quelle
Sprechen Sie über das Veröffentlichen oder Überprüfen Ihrer Idee? Was meinst du mit "Ressourcen"; Zeitschriften oder Kontrollmittel?
Raphael
12
Es scheint mir, dass wenn das Veröffentlichen das Ziel ist, Sie mindestens eine Laufzeitanalyse haben müssen und ein Gefühl dafür haben müssen, wie richtig Ihr Algorithmus ist, vorausgesetzt, es ist eine Heuristik. Sie müssten auch vergleichen, was Ihr Algorithmus mit früheren Arbeiten macht - ohne das ist die Veröffentlichung ein Nein-Nein. Tatsächlich würde ich empfehlen, dies zuerst zu tun.
Suresh Venkat
Ich denke über eine Veröffentlichung nach, aber im Moment suche ich wirklich Hilfe bei der Analyse. Mir ist klar, dass diese Website bei bestimmten Fragen hilfreich sein kann, aber ich hoffe, Orte zu finden, an denen ich Leute treffen kann, die bereit wären, bei der Analyse zu helfen. Ich habe auch nicht viel Hintergrundwissen über andere Algorithmen, aber ich frage mich, ob mein Ansatz etwas Einzigartiges sein könnte.
Matt Groff
Siehe auch verwandte Frage cstheory.stackexchange.com/questions/7600/…
András Salamon

Antworten:

32

Wenn Ihr SAT-Algorithmus praktisch sein soll, sollten Sie den ausführen SAT-Wettbewerbsbenchmarks . Die SAT-Lösungsgemeinschaft wird Ihre Arbeit viel ernster nehmen, wenn Sie zeigen können, dass Ihr Ansatz mit vorhandenen Lösern konkurrenzfähig ist. Ihr Solver muss nicht schneller als jeder Solver sein oder mehr Instanzen lösen, aber er sollte ein ernsthafter Konkurrent sein. Sie benötigen keine sehr schnelle oder leistungsstarke Maschine, um die Benchmarks auszuführen. Sie können die Laufzeit einfach mit einem der kostenlosen SAT-Löser wie MiniSAT oder PicoSAT vergleichen . Mit diesen Lösern können Sie auch sehen, wie die Antworten aussehen sollten.

Wenn Sie an einem praktischen Löser arbeiten, der neue Techniken verwendet, und Ihr Ansatz noch nicht wettbewerbsfähig ist, würde ich dennoch empfehlen, diese Benchmarks auszuprobieren. Sie würden Ihnen helfen, die Art der Probleme zu verstehen, die Sie lösen möchten, und die Art der Leistung, die Sie anstreben sollten. Vielleicht möchten Sie auch einige der wichtigsten Kapitel des Handbuchs zur Zufriedenheit oder der kürzlich durchgeführten Umfrage lesen

  • Knot Pipatsrisawat und Adnan Darwiche über moderne Lösungslöser für das Lernen von Klauseln , Journal of Automated Reasoning 44 277–301, 2010. ( PDF )

um die Arten von Argumenten zu sehen, die die wichtigsten Löser unterstützen. Wenn Sie neue Ideen haben, die noch nicht für die Leistung optimiert sind, sowie die besten Löser, müssen Sie die potenziellen Vorteile Ihres Ansatzes jemandem erklären, der die lange Abfolge theoretischer Überlegungen kennt, die zu den aktuellen "Besten" geführt haben üben "Designentscheidungen.

Wenn Ihr Beitrag rein theoretisch ist, müssen Sie sich der vielen Artikel in diesem Bereich bewusst sein und in Ihrem Artikel erklären, warum Ihr Ansatz zumindest in gewisser Weise besser ist. Werfen Sie einen Blick auf aktuelle Arbeiten von beispielsweise Amin Coja-Oghlan oder Alan Frieze, um ein Gefühl für den Stand der Technik zu bekommen und nützliche Hinweise auf wichtige Artikel zu erhalten.

András Salamon
quelle
Siehe auch die Diskussion unter cstheory.stackexchange.com/questions/1719/…
András Salamon
Siehe auch die Diskussion unter cstheory.stackexchange.com/questions/7600/…
András Salamon
2

Da Sie jetzt Ihren Algorithmus teilen möchten, lautet mein persönlicher Vorschlag: Erstellen Sie eine sehr einfache Website. Die Site sollte diese 2 Dinge zur Verfügung stellen:

  1. Der Quellcode des Algorithmus.
  2. Ein Dokument, das Ihren Ansatz kurz beschreibt. Wo ist Ihr Ansatz anders? Welches ist die neue Idee dahinter? Dieses Dokument muss weder ein perfekt geschriebenes technisches Dokument sein noch einen formalen Beweis enthalten: Eine PowerPoint-Präsentation würde ausreichen, um den Kern Ihrer Idee zu "übermitteln". Erklären Sie uns einfach, warum Ihr Algorithmus Ihrer Meinung nach anders ist. Vielleicht ist es einzigartig, wer weiß.

Giorgio Camerani
quelle
Ich halte das Erstellen einer Website nicht für eine sehr gute Idee. Weil viele Leute eine Website erstellen, wenn sie denken, sie hätten große Probleme gelöst oder TOE gefunden. zB dharwadker.org/tevet/isomorphism matpitka.blogspot.com Satz: "Für jedes ungelöste Problem gibt es mindestens einen Mann, der behauptet, er habe es gelöst und eine Website erstellt." Schlechte Idee -1 :(
Pratik Deoghare
@TheMachineCharmer: So etwas habe ich nicht gemeint. Die Website war nur eine Möglichkeit, den Code herunterzuladen und das Dokument zu lesen, in dem der Algorithmus beschrieben wird. Ich meinte nicht eine "feiernde" Website. Stattdessen meinte ich eine Website, auf der lediglich Material ohne "triumphalen" Anspruch geteilt werden soll (ähnlich wie in Ihrer Antwort, obwohl Ihre etwas "offizieller" ist).
Giorgio Camerani
1
  1. Sie können Ihre Ideen im Standardpapierformat aufschreiben.
  2. Veröffentlichen Sie es auf ArXiv .
  3. Teilen Sie den Quellcode auf github .
  4. Verbringen Sie einige Zeit mit dem Erlernen der Laufzeitanalyse und aktualisieren Sie Ihr Papier, wenn Sie fertig sind.

zB Sie können ein Umfragepapier schreiben und am Ende Ihre Lösung als neuen vielversprechenden Ansatz vorschlagen. Aber ohne Korrektheitsnachweis und Laufzeitanalyse werden es nicht viele Menschen ernst nehmen (aber einige werden es).

Pratik Deoghare
quelle