Computational Complexity

We're seeing an attack on capitalism on both ends of the political spectrum with with the election of Democratic Socialist Zhoran Mamdani as mayor of New York, and Donald Trump trying to direct the economy through tariffs, less independency of the Federal Bank and partial government control of companies such as a nearly 10% ownership of Intel and the "golden share" of U.S. Steel.

Now I'm not an economist and there are many arguments for and against socialism and capitalism, especially in their purest forms. I want to focus on the complexity of the economy. Let's start by considering rent control.

It starts with the worthy goal of preventing people from having to leave their apartments because of rising rents due to market demand. So you limit the rent increases and the ability to evict current residents. But this could cause landlords to cut back on improvements, not prioritize service and repairs, or build new properties to increase the supply. So you have to give landlords incentives to do these things, leading to other issues which leads down a rabbit hole. I saw extreme rent control in Berkeley in the 1980s and a lack of available housing forced me to live 13 miles away.

That's just rent control in a single city. Other attempts to control the economy will lead to unexpected inefficiencies and you can't predict markets enough to catch them.

The 1920 essay Economic Calculation in the Socialist Commonwealth by Ludwig von Mises argued that market prices give critical information for companies and individuals to make decisions. I think of it like a circuit, where the prices are values of intermediate gates so that we can have simple operations at every level leading to a very complex behavior in the aggregate, much like a neural net today. Frederick Hayek went further in his 1945 essay The Use of Knowledge in Society that a center planner couldn't adapt with the speed of change in the markets.

Could today's neural nets replace the need for these intermediate pricing and adapt quickly? It's really a combination of the two, many companies are using sophisticated machine learning models that lead to more accurate pricing, adding to the efficiency of markets.

Capitalism has its challenges: Companies can shrink or close, people can lose their jobs and we need good safety nets. Government has a role to protect safety, enforce contracts and provide services and some control where competition doesn't scale, like utilities and pubic transportation. Government also has a role in promoting public goods including education, scientific research and national defense.

While neither Mamdani or Trump want anything close to complete government control of the economy, I still worry that even their limited influences will hurt innovation and in the longer run hurt the very people these policies are meant to help.

The following excerpt from Abrahim Ladha's comment on Lance's post about
AI and intro theory caught my attention:


---------------------------
BEGIN EXCERPT

Not just with AI, but in theory and math courses, there have always been Bart Simpson
level questions by students of the form

"Why do I need to know this?

like

Why do I need to know my times tables when the calculator does this for me?

There has never been a good answer because these students already do not have an open mind.
Euclid was asked such a question once and said something like

give him a penny so he may feel like he earned something for what he learned.

END EXCERPT
-----------------------------------

He gives a quote by Euclid.

1) I have heard that Euclid might not have really existed.

2) I have never heard that quote.

I asked Abrahim Ladha if he had a source for the Euclid quote.

I never go a response.

I asked chatty:

What is the historical evidence that Euclid existed?

and also

Did Euclid say give him a penny so he may feel like he earned something for what he learned?

The answer to both questions are below. The bottom line is that

1) Euclid might not have existed.

2) The idea underlying the quote is attributed to him. The exact quote is modern rendering.

Should Abrahim have consulted chatty before making his comment.

1) YES, it's important to make sure your facts are correct.

2) NO, his point is still valid. (That is a slippery slope.)

----------------------------------------
BILL: What is the historical evidence that Euclid existed?

That’s a great question — and a surprisingly tricky one.

Short answer

There is no direct historical evidence that Euclid (often called Euclid of Alexandria) existed
as an individual in the way we can verify the existence of, say, Archimedes. What we “know”
about Euclid comes almost entirely from later sources, not from contemporary records.

The evidence we do have

1)
Type: Ancient testimonies

Source: Proclus, Commentary on the First Book of Euclid’s Elements

Date: ca. 450 CE

Note: Written about 700 years after Euclid’s supposed lifetime. Proclus says Euclid lived
in the time of Ptolemy I (reigned 323–283 BCE) and taught in Alexandria. This is our main source.

2)
Type: Mentions by other ancient authors

Source: Pappus of Alexandria (4th century CE), Diogenes Laërtius (possibly), and others

Date: 200–600 years later

Note: These references repeat information similar to Proclus’s account — that Euclid compiled
the Elements and worked in Alexandria.

3)
Type: Mathematical evidence

Source: The Elements and other works attributed to Euclid (Data, Optics, Phaenomena, etc.)

Date: ca. 300 BCE?

Note: These texts show a unified style and method, suggesting a single organizing mind
(or school). But there is no personal or biographical detail inside them.

4)
Type: Absence of contemporary evidence

Note: There are no letters, inscriptions, or administrative records naming Euclid. No ancient
biography (unlike Archimedes or Apollonius).

Scholarly interpretation

Traditional view: There was a historical Euclid, a mathematician who worked in Alexandria
around 300 BCE and compiled earlier Greek geometry into the Elements.

Skeptical or revisionist view: “Euclid” may have been a collective name for a team or a
school of mathematicians in early Hellenistic Alexandria, much like “Hippocrates” in medicine.

The Elements itself is consistent in style, so even if multiple people contributed, it was
edited or systematized by someone with extraordinary coherence and rigor.

In summary

There is no direct documentary or archaeological proof that Euclid existed as an individual,
only later testimony and internal evidence from the mathematical works. Historically, most
scholars accept that there was a person — or at least a leading mathematician — behind the
name “Euclid,” but his life remains almost entirely unknown.
---------------------

BILL: Did Euclid say

`give him a penny so he may feel like he earned something for what he learned.'

ChatGPT said:

The quote you’re referring to — something like “Give him a penny so he may feel he has learned
something” — is attributed to Euclid, but not in those exact modern words.

It comes from an ancient anecdote recorded by Proclus (a 5th-century commentator on Euclid) in
his Commentary on Euclid’s Elements. The story goes like this:

A student, after learning the first theorem of geometry, asked Euclid,

“What shall I get by learning these things?”

Euclid called his slave and said,

“Give him a penny, since he must make gain out of what he learns.”

In Greek, it’s roughly:

“Δός αὐτῷ ὀβολόν, ἐπειδὴ κερδαίνειν δεῖται ἀπὸ τῶν μαθημάτων.”

So your paraphrase captures the spirit of the anecdote — Euclid was mocking the idea of
studying geometry for material reward — but the exact wording

“give him a penny so he may feel he earned something for what he learned”

is a modern retelling, not a direct quotation.

I sometimes give the following advice for research which I label Bill's Bad Advice. We will later see who it might be good advice for. Spoiler alert: the number of people for whom it is good advice is shrinking but might include Lance especially now (see his post about stepping down from admin, here).

When you come across a possible research topic or problem, or have some idea, and are wondering if you want to pursue it, here is my bad advice:

1) DON"T CARE if anyone else cares. If YOU care then that is enough to at least get started.

2) DON"T CARE if it has the potential for a published paper. FIRST do the work then, if you feel like it, look for a good venue. You might not bother if posting to arxiv or making an open problems column out of it or a (guest) blog post out of it is a good endpoint. (I run the SIGACT News Open Problems Column- feel free to contact me if you want to submit one.)

3) DON"T CARE if it has practical implications.

4) DON"T CARE if you can get a grant for it. With the current state of the NSF this advice may soon become irrelevant.

5) DON"T CARE if someone else already did it (though at a later stage you should check on this). Even if you work on it and find someone else did it, you will have LEARNED about the problem through your efforts. You might then want to do a survey for your own benefit to consolidate your knowledge.

Why should you NOT CARE about any of these things? Because they get in the way of actually DOING something.

Here are two examples of when this approach WORKED and one where it DID NOT WORK, though both classifications might depend on your definition of WORKED.

WORKED: My work on Muffins. All I wanted was to get some High School and Undergraduate Projects out of it. I ended up with a book on it which made me twenty dollars last year! More to the point, I learned a lot, as did my co-authors and I am happy with the book. The co-authors were Undergraduates so my dept put me up for a mentoring award (I have other credentials as well). I did not win, but I got a nice letter saying they had many qualified applicants. OH- it didn't say if I was one of them.

WORKED: I have had many Ramsey Projects where a High School Student codes stuff up and learns some Ramsey, some coding, and gets the experience of research. Sometimes they do a survey paper or open problems column. We both learn A LOT from this and the student gets a good letter from me. Do they do something NEW? Publishable? No, though some surveys and open problems columns have come out of this. I DO tell them ahead of time that the work is unlikely to lead to original results (and hence unlikely to be good for a science competition).

DID NOT WORK: See this blog post here about the math and here about finding out that the problem we were working on was already known and more was known than we thought. I didn't mind this, but one of the authors did.

Note that WORKED and DID NOT WORK also depend on your goals.

For whom is this bad advice? Good advice?

1) It was always bad advice for young assistant professors who need to get papers and grants to get tenure.

2) Hypothetically, once you get tenure you have job security and hence can change fields or follow my bad advice without consequences. But with grants and salary and teaching load issues, this is less the case. Perhaps I am nostalgic for a time that never was.

3) High School Students were my main audience for bad advice. It's not as important for them to get papers out as for (say) assistant professors. But even this is changing. Colleges are getting more competitive. And HS students may well want a project that can lead to Science competitions. I am not going to say things were better when I was a kid but instead pose non-rhetorical questions:

a) Are high school students getting into research earlier than they used to? I am sure the answer is yes.

b) Are we losing the safe space where a high school student can just learn things and do things and not worry so much about if it's publishable? Yes, but I am not sure how widespread that is.

c) If we are losing that safe space, is that a bad thing?

d) Points a,b,c apply to ugraduates who want to go to graduate school more than for high school students who want to go to college.

4) Full Professors may have more freedom to follow my bad advice. Lance is looking for things to do now that he is no longer a dean, and indeed, is back to being a teaching-and-research professor. So he might follow my advice. However, he actually cares if people care about his work. He does not have to follow all of my advice, but he can follow some of it.

This fall, for the first time at Illinois Tech, I'm teaching Introduction to Theory of Computation. While I've taught a variation of this course a couple dozen times, I last taught this class Spring 2016 at Georgia Tech. Intro Theory is a course whose main theorems don't change but it feels different in the AI era.

Here are the big and little things for me.

NP as a Hard Problem?

Garey and Johnson's classic 1979 book on NP-completeness had this famous cartoon.

Several people emailed me that September 16, 2025---written as 9-16-25 in the US---represents the integer side lengths of a right triangle.

9-16-25 is the only such triple that is also a valid date. This kind of mathematical alignment only happens once every 100 years. The next occurrence will be September 16, 2125.

Since this is such a rare event, let's explore some more math-themed dates.

1) Pythagorean Triples That Work as Future Dates

Note that 9-16-25 is not a Pythagorean triple; however, 3-4-5 is.

Here are some future dates that are both Pythagorean triples and valid calendar dates:

March 4, 2105 is 3-4-5

May 12, 2113 is 5-12-13

June 8, 2110 is 6-8-10

July 24, 2125 is 7-24-25 (Darn---July 24, 2025 was recent and I missed it!)

August 15, 2117 is 8-15-17

I think that's it. Recall that we need the month to be in \(\{1,\ldots,12\}\) and the day to be in \(\{1,\ldots,31\}\) with some exceptions:

Thirty days has September, April, June, and November

All the rest have thirty-one,

Excepting February, fun!

And that has twenty-eight days clear

And twenty-nine in a Leap Year

There are 24 versions of this poem at a website which is here.

2) Why Didn't Anyone Email Me About Earlier Dates?

I wonder why nobody emailed me on, say, March 4, 2005 (3-4-5). That's a Pythagorean triple, but maybe it just looked like three consecutive numbers. Oh well.

And what about May 12, 2013 (5-12-13)? That's a really cool Pythagorean triple. Oh well.

3) Other Math-Related Dates Using Month, Day, and Year.
So dates like Pi Day don't count---we want the full date to be interesting mathematically. Side note---I looked up how Pi Day is referred to and its Pi Day, not \(\pi\) day. Probably because not all typesetting systems can easily produce \(\pi\).

In 2001 I supervised Charles Lin's Master's Thesis, which was on Private Information Retrieval.

In 2025 I supervised Charles Lin's Master's Thesis, which was on Ramsey Theory.

These are different people. To celebrate the second one's thesis, I took them both out to lunch together.

A Picture of Charles, Charles, and Bill is here.

I asked ChatGPT about common names.

1) ChatGPT tells me (and I believe them) that the number of people in American named Charles Lin is between 200 and 900. The answer pointed out that Charles is common and Lin is common but the combination is not common.

2) ChatGPT tells me (and I believe them) that the number of people named John Smith is between 25,000 and 40,000. I've heard it's a common name, but I do not know anyone named that. How is that possible?

3) I predict that people with last name Smith will be reluctant to name their child John because it is so common. Hence this name will decline. However, I made that same prediction 40 years ago. Maybe it did decline TO 40,000.

4) The most common boys' names in 2025 (so far) in the US are, in order:

Liam, Noah, Oliver, Theodore, James, Henry, Mateo, Elijah, Lucas, William

According to this website here, the five most common boys' names in 1960 (the year I was born), in order, are

David, Michael, John, James Robert.

James is the only on both lists.

I don't have the next five, though I suspect Henry and William would be on it. I also suspect that Liam and Mateo would not be in the top 100.

5) The most common girls' names in 2025 (so far) in the US are, in order:

Olivia, Emma, Amelia, Charlotte, Mia, Sophia, Isabella, Evelyn, Ava, Sofia

(Should they have Sophia and Sofia both on the list? I would say yes but it is odd.)

According to that same website, the most common girls' names in 1960 (the year I was born), in order, are

Mary, Susan, Linda, Karen, Donna.

None of the 1960 name are on the 2025 list. I suspect that would still true for the next 10.

6) When I was in grade school if the teacher said Quiet down Bill and Lisa the class went quiet.

7) The most common first name in the world is Mohammad. The most common last name in the world is Wang. Hence the most common name in the world has to be Mohammad Wang. I've asked students to find the flaw in that logic and all 8 Mohammad Wangs in my class found the flaw. Kudos to them! (Darling says I should always tell you when I am kidding. I am kidding. Only 2 of the 8 Mohammad Wangs in my class found the flaw.)

8) (ADDED LATER) One of my readers emailed me the following two items

a) From The Big Bang Theory

Howard: It gets better. Someone has to go up with the telescope as a payload specialist, and guess who that someone is.

Sheldon: Mohammed Lee.

Howard: Who’s Mohammed Lee?

Sheldon: Mohammed is the most common first name in the world, Lee, the most common surname. As I didn’t know the answer, I thought that gave me a mathematical edge.

b) As an interesting aside, I noticed that this semester I have three students named "Luke" and three named "Ben" which made me notice that kids who grew up with the original Star Wars movies would have kids in college around now (but none of my current students are named "Leia")

9) (ADDED LATER) I HEARD that the name `Barack' was popular when he was president.

I looked it up:

5 babies got that name in 2007

52 babies got that name in 2008

69 babies got that name in 2009

it declined since then.

BAD SCIENCE TIME: The number of babies named Barack increased 10-fold from 2007 to 2008.

TRUE but not significant.

10) I hope to supervise at least one more Charles Lin before I retire.