Mea Culpa

Gödel’s Lost Letter and P=NP 2020-08-31

Plus more on the separating word problem

Mea Culpa is not someone we introduced on the blog before. She does not come from the same world as Lofa Polir or Neil L. As in the French movie poster at right, the meaning is “my fault.”

Today we apologize for some oversights and hasty omissions regarding the last post. Then we will explain Dick’s “laws with errors”.

Let’s be clear. The paper we discussed in the last post claiming an order ${\log n}$ upper bound is wrong. The best upper bound is still due to Zachary Chase and is order ${n^{1/3}}$ , with some log’s.

At GLL we try to be fair and upbeat, especially with proof attempts. We know how hard it is to put yourself out there when you claim a new result. Whether for a famous open problem or not, it is always difficult. Mistakes are possible, miss understandings are possible.

But perhaps this time we have gone too far, and for that we apologize. We just love the SWP, and want to reiterate the idea the post was supposed to be (only) about, an approach to SWP.

There is also Nostra Culpa—“our fault,” Ken says too. Not only is there a short film with that title, there is a 2013 one-singer opera of that title with libretto drawn from a 2012 Twitter feud between the economist Paul Krugman and the president of Estonia. At least our issue did not break out on Twitter. We were instead contacted privately by some friends who knew more about the erroneous paper highlighted in our post. We could have contacted them first—that was our omission.

Again sorry for any confusion we created. Let’s turn to the approach we want to share about SWP.

Laws with Errors

I think there is hope that positive laws must be large, especially if we extend what it mean by a law. Consider a positive law

$\displaystyle U = V,$

where ${U}$ and ${V}$ are words over the letters ${A}$ and ${B}$ . Recall we can tell if ${U}$ and ${V}$ are different provided there is a finite group ${G}$ so that for some ${A,B}$ in ${G}$ the value of ${U}$ and ${V}$ are different. This can be computed by a FSA with at most order ${|G|}$ states. So the smaller ${|G|}$ is the better.

The trouble is it does not seem to the case that strong enough lower bounds are known for positive laws. This suggest that we make it harder for a law to work.

The idea is to use a FST, that is a finite state transducer. This is a finite state device that reads a symbol, updates its state, and outputs one or more symbols. If ${T}$ is the FST and ${U}$ is a string, let ${T(U)}$ be the result of applying ${T}$ . For example, suppose that ${ABBBAB}$ is an input ${U}$ . Let the transducer add a ${C}$ after each ${AB}$ . Thus ${U}$ maps to:

$\displaystyle ABCBBABC.$

Then the following is true:

Lemma 1 Let ${G}$ be group and let ${T}$ be a transducer with ${S}$ states. Then we can separate ${U}$ from ${V}$ by a FSA with order ${|G| \cdot S}$ states provided
$\displaystyle T(U) = T(V)$
is not a law in ${G}$ .

Proof: The key is to simulate ${T}$ as we read the input, and at the same time update the group element. This can be done by a FSA with the product ${|G|}$ and ${S}$ states. $\Box$

Open Problems

The hope is that having a law that is invariant for all FST, even only those with few states, is difficult.

A conjecture: Positive laws that can handle all FST transducers with ${n^{\epsilon}}$ states must be large.

That is are large enough to advance our best bounds on SWP. What do you think?