⋆｡ﾟ🪐｡⋆｡ﾟ ℂ𝕃𝔸𝕌𝔻𝔼 & 𝔽ℝ𝕀𝔼ℕ𝔻𝕊 𝕀ℕℂ. 🛸 ⋆｡ﾟ☾

Peano Arithmetic is sound iff this Turing Machine ω-accepts. The red and green transitions emit 0 and 1 bits that represent records in a two-player game. One player is the "challenger"; the other is the "defender". PA is sound exactly when the defender has a winning strategy. Proofs are incoming. This machine is smaller than my 238-state PA consistency machine because it incorporates ideas from @ereliuer_eteer 's 208-state one. So we're adding 28 states to represent this game and soundness.

It's over for @OpenAI unless they release a Millennium Prize Problem-solving math model. The new Fable or Muse Ember or whatever are just too powerful unless we get Bel and a proof of the Riemann Hypothesis and generous ChatGPT Pro rate limits to clear any math problem backlogs.

This isn't really new, but it's cute putting them together. Varying q gives you problems in P, post-selected classical power, and post-selected quantum power. If A was generated from a quantum circuit, it's BQP-complete.

"The Immerman–Szelepcsényi theorem states that nondeterministic space complexity classes are closed under complementation" "NL = coNL" Since it is believed NP != coNP, there would be an asymmetry between time and space complexity.

Problem 0211: Exact Zero-Free Permanent Representations of #SAT #SAT has a value-preserving reduction to computing the permanent of a matrix with entries {-1,0,1/2,1}. {-1,1} is impossible by parity. {-1,0,1} would imply ⊕P = P, and hence NP = RP by the Valiant–Vazirani isolation theorem. {-1,1/2,1} is open. {-1,1/k,1} with k varying per instance has an almost-reduction: There is a signed integer permanent reduction, replace the zeros with 1/k and change the scales, and then round the answer. An exact value-preserving reduction is open. This is a math problem on my list for upcoming AI models.

The number of Latin square completions with h holes and t symbols can be written as the permanent of a matrix with size t+2h taking values {-1,0,1/2,1} github.com/Mira-Cult/math/bl…

The permanent of an arithmetic-progression circulant matrix can be computed in O(n⁵) arithmetic operations and O(n⁴) working storage. github.com/Mira-Cult/math/bl… In high school, I worked on finding polynomial-time algorithms for permanents of many special classes of matrices. Arithmetic-progression circulant matrices were on the list, but I never solved them. Astra solved it right away: There's a recurrence with counters. I got excited that it was finally solved, but when checking for prior art apparently it's a corollary of a 2010 paper that proves a more general theorem for "bounded cliquewidth". It doesn't appear to have been stated for this exact family, though.