この間、Vladimir Fedorovichと私は、仲間の科学者に送るための記事のバージョンを準備し、同時にこのアルゴリズムのリファレンス実装をJavaで実装しました。
科学者への記事と公開書簡
記事の基礎として、私たちは英語の既存の出版物を取り上げ、以前の投稿でリンクを付けました。 現在のバージョンは小さな追加のみが異なります。これは、私たちの意見では、アルゴリズムと提供された証拠の理解を単純化するはずです。 kichikのアドバイスにより、この記事はarXiv.orgで公開されました。
不一致構造に基づく非正統的な組み合わせモデル
arxiv.org/abs/1011.3944
本日、公開レターを作成しました。このレターは、連絡先が見つかった一部の科学者に送信されました（リンクについてはalexeyromに感謝します）。 この手紙はサイトでも公開されており、特に議論のために作成しました。
3-SAT：新規モデル
romvf.wordpress.com/2011/01/19/open-letter
このテーマに関係する科学者の連絡先がある場合は、この手紙を送ってください。 フィードバックやコメントを歓迎します。
Javaでのリファレンス実装
この記事の新しいバージョンに取り組みながら、Javaでリファレンス実装を作成するアルゴリズムを見つけました。 やった！ LGPLバージョン3のライセンスの下で、11月19日にgithubで公開したアプリケーションの最初のバージョン：
ブール3-SAT問題に対するロマノフの多項式アルゴリズムの参照実装
github.com/anjlab/sat3
これはシングルスレッド実装であり、 DIMACS CNFファイルから式を読み取り、式が実行可能な場合は実行セットを出力し、式が実行できない場合は対応するメッセージを出力するコンソールアプリケーションです。 このプログラムは詳細なログを保持しており、記事の読者がアルゴリズムを理解するのに役立ちます。
シードについては、記事の例（左）と変数の数が100の数式（右、クリック可能）の実行セットを含む基本的なグラフです。
| 
|
アプリケーションの結果の詳細については、 こちらをご覧ください 。 githubにはreadmeがあり、アプリケーションの実行方法を説明するいくつかのwikiページがあります。
最新の公開バージョンは1.0.3です。 ただし、HEADには、アプリケーションを2倍高速化する追加の最適化がいくつか含まれています（バージョン2.0.0-SNAPSHOT）。
次は何ですか
さらに作業をいくつかの領域に分けることができます。
- できるだけ多くの関心のある人々にそれを示すための記事の普及。
ここで、Habrの助けを期待しています。 また、科学雑誌への記事の公開にも取り組みますが、現在いくつかのオプションがあります。
- 生産的な実装を作成します。
リファレンス実装は、元々、アルゴリズムの操作に慣れるための読者への支援として考案されました。 Javaを実行できる任意のパーソナルコンピュータで動作することが想定されていました。 大規模な産業上の問題を解決するようには設計されていません。
一方では、これはアルゴリズムの計算の複雑さ（O（n ^ 4 * m））、他方ではリソースの制限、特にRAMによって妨げられます。 ここにはいくつかの開発パスがあります：データ構造とアルゴリズムの最適化、およびアルゴリズムの並列化（複数のスレッド、プロセスなどへ）。
あなたがこれを手伝いたい場合-書く、私たちは協力する方法を探します。
- 適用された問題の解決。
3-SPの問題自体は純粋に理論的なものですが、他の多くの適用された問題もそれに帰着します。 これは個々の研究のトピックですが。