IdeaWell

Project ideas from Hacker News discussions.

A SAT Attack on Tarski's High School Algebra Problem

Original Article

Hacker News Discussion

📝 Discussion Summary (Click to expand)

1. Subtraction excluded from the algebra

"We’re in the semiring of positive integers, so there are no additive (or multiplicative) inverses." — Sharlin
The discussion stresses that subtraction isn’t part of the algebra because it isn’t closed over positive integers, making the “high‑school algebra (excluding subtraction)” framing necessary.

2. Using Wilkie’s counterexample to prune the search

"They use the properties of Wilkie's counterexample to restrict the search space. So you can’t just pick arbitrary identities that hold over the positive integers and repeat the process until you’ve found a smaller model." — yorwba
Researchers exploit Wilkie’s specific counterexample to limit the identities they test, rather than exploring an unrestricted space of equational candidates.

3. Decidability, finite axiomatizability, and Gödel’s relevance

"No, Gödel's incompleteness theorem applies to theories that can interpret first‑order arithmetic..." — LegionMammal978
The thread clarifies that the equational theory of positive integers with addition, multiplication, and exponentiation is decidable but not finitely axiomatizable, and Gödel’s incompleteness does not apply to this purely equational setting.

🚀 Project Ideas

Identity Search Engine for Algebraic Structures

Summary

  • Automated generator of minimal counterexamples for equational theories such as Tarski’s problem.
  • Lets researchers test new axioms without manual SAT encoding.

Details

Key Value
Target Audience Theoretical computer scientists, mathematicians, graduate students
Core Feature Counterexample discovery with built‑in SAT encoding and auxiliary variable optimization
Tech Stack Rust backend, TypeScript/React front‑end, MiniSat solver, Docker
Difficulty Medium
Monetization Revenue-ready: Subscription $15/month

Notes

  • HN users asked for systematic ways to search identities and cited SAT variable grouping tricks.
  • Addresses frustration that manual search is tedious and error‑prone.

Interactive Semiring Designer

Summary

  • Visual editor for defining algebraic structures like semirings and highlighting missing operations.
  • Helps users understand why subtraction is excluded and how to build consistent models.

Details

Key Value
Target Audience Undergraduate math students, math enthusiasts, educators
Core Feature Real‑time closure checking and axiom suggestion engine
Tech Stack Python/Flask backend, D3.js visualizer, SQLite storage
Difficulty Low
Monetization Hobby

Notes

  • Commenters complained that “High School Algebra (Excluding Subtraction)” isn’t catchy; they’d love an intuitive UI.
  • Provides practical utility for teaching and experimentation.

Algebraic Identity SAT Checker

Summary

  • Web API that encodes arbitrary algebraic identities into SAT problems with auxiliary variables.
  • Streamlines the process described in recent counterexample papers.

Details

Key Value
Target Audience SAT developers, logic hobbyists, algorithm researchers
Core Feature Bulk identity encoding and result retrieval via REST
Tech Stack Node.js/Express, MiniSat wrapper, Redis queue
Difficulty Medium
Monetization Revenue-ready: Pay-per-call $0.001 per check

Notes

  • Users praised auxiliary variable techniques for reducing clause count; this tool makes them accessible.
  • Enables quick experimentation with large identity sets.

Read Later