HN 日本語サマリー

← 一覧へ戻る
科学・技術

タルスキの高校代数問題に対するSAT攻撃

A SAT Attack on Tarski's High School Algebra Problem (arxiv.org)

87 pointsby matt_d35 コメント

要約

本論文では、タルスキの高校代数問題における最小の反例モデルのサイズが12であることをSATソルバーを用いて証明した。さらに、12要素の反例モデルが8,957,952個存在することを示し、それらの分類も行った。このSATアプローチは、既存の専用ツールよりも優れており、結果の正しさはLeanで自動形式化により証明されている。

全文翻訳

数学 > 論理学

arXiv:2608.08421 (math)

[2026年8月9日提出 (v1)、最終更新2026年9月2日 (本バージョン、v2)]

タイトル: A SAT Attack on Tarski's High School Algebra Problem

著者: Bernardo Subercaseaux, Benjamin Przybocki

Bernardo SubercaseauxとBenjamin Przybockiによる論文「A SAT Attack on Tarski's High School Algebra Problem」のPDFを表示します。

PDFを表示 HTML (実験的)

要旨: タルスキの高校代数問題は、正の整数における加算、乗算、べき乗に関するすべての真の恒等式が、11個の初等恒等式のリストから導かれるかどうかを問うものである。驚くべきことに、Wilkieは以下の恒等式が正の整数上で有効であるが、タルスキの公理からは導かれないことを示した。
\begin{align*}
&\left((1+x)^y + (1+x+x^2)^y\right)^x \cdot \left((1+x^3)^x + (1+x^2+x^4)^x\right)^y = \
&\left((1+x)^x + (1+x+x^2)^x\right)^y \cdot \left((1+x^3)^y + (1+x^2+x^4)^y\right)^x.
\end{align*} Gurevičは59個の要素を持つ代数系を与え、それはタルスキの公理を満たすがWilkieの恒等式は満たさない。長年にわたり、いくつかの著者がそのような反例モデルのサイズを縮小し、最終的にはBurrisとYeatsによるサイズ12の反例モデルに至った。一方、Zhangは11個未満の要素を持つ反例モデルは存在しないことを証明した。SATソルバーを用いることで、我々は最小の反例モデルがBurrisとYeatsが予想した通りサイズ12であることを証明した。さらに、同型を除いて12個の要素を持つ反例モデルがちょうど8,957,952個存在することを示し、それらの単純な分類を提供した。我々のSATアプローチは、等式理論における反例モデルを見つけるための専用ツールであるMace4およびSEMよりも優れた性能を発揮した。さらに、自動形式化を用いて、Leanにおける我々の主要な結果の正しさを証明した。

コメント:21ページ。LPAR 2026に採択。v2はarXiv:2608.16406を認識し、軽微な誤植を修正しています。
件名:論理学 (math.LO); 計算機科学における論理学 (cs.LO)
引用:arXiv:2608.08421 [math.LO]
(または本バージョンについては arXiv:2608.08421v2 [math.LO])
https://doi.org/10.48550/arXiv.2608.08421 arXiv発行のDOI (DataCite経由)

投稿履歴

From: Bernardo Anibal Subercaseaux Roa
v1 日, 2026年8月9日 02:32:31 UTC (32 KB)
v2 水, 2026年9月2日 21:56:34 UTC (34 KB)

全文リンク:

論文アクセス

Bernardo SubercaseauxとBenjamin Przybockiによる論文「A SAT Attack on Tarski's High School Algebra Problem」のPDFを表示します。

ライセンスを表示

現在の閲覧コンテキスト:

math.LO

< 前   |   次 >

新規 | 最近 | 2026-08

以下で閲覧を変更:

cs
cs.LO
math

参考文献と引用

読み込み中...

BibTeX形式の引用

読み込み中...

提供元:

ブックマーク

[画像: BibSonomy][画像: Reddit]

書誌ツール

書誌および引用ツール

書誌エクスプローラー トグル

書誌エクスプローラー (エクスプローラーとは?)

コネクテッドペーパー トグル

コネクテッドペーパー (コネクテッドペーパーとは?)

リットマップス トグル

リットマップス (リットマップスとは?)

scite.ai トグル

scite Smart Citations (スマート引用とは?)

コード、データ、メディア

本論文に関連するコード、データ、メディア

alphaXiv トグル

alphaXiv (alphaXivとは?)

コードへのリンク トグル

CatalyzeX論文コードファインダー (CatalyzeXとは?)

DagsHub トグル

DagsHub (DagsHubとは?)

GotitPub トグル

Gotit.pub (GotitPubとは?)

Huggingface トグル

Hugging Face (Hugging Faceとは?)

ScienceCast トグル

ScienceCast (ScienceCastとは?)

デモ

デモ

Replicate トグル

Replicate (Replicateとは?)

スペース トグル

Hugging Face Spaces (Spacesとは?)

スペース トグル

TXYZ.AI (TXYZ.AIとは?)

関連記事

レコメンダーおよび検索ツール

インフルエンスフラワーへのリンク

インフルエンスフラワー (インフルエンスフラワーとは?)

コアレコメンダー トグル

CORE Recommender (COREとは?)

  • 著者
  • 会場
  • 機関
  • トピック

arXivLabsについて

arXivLabs: コミュニティ協力者との実験的プロジェクト

arXivLabsは、協力者がarXivの新しい機能を直接ウェブサイト上で開発・共有できるフレームワークです。

arXivLabsで働く個人および組織は、オープンさ、コミュニティ、卓越性、ユーザーデータプライバシーという我々の価値観を受け入れ、遵守しています。arXivはこの価値観にコミットしており、それに準拠するパートナーのみと協力します。

arXivコミュニティに価値をもたらすプロジェクトのアイデアがありますか? arXivLabsについてもっと知る。

この論文の著者は誰が推薦者ですか? | MathJaxを無効にする (MathJaxとは?)