You are viewing the historical archive of The Philosophy Forum.
For current discussions, visit the live forum.
Go to live forum

Is there a unit of complexity in mathematics?

Shawn October 14, 2021 at 23:57 3300 views 9 comments
I have been struggling with a thought of mine as of recent about complexity in mathematics.

I see no need for long posts, which I struggled with previously, but want to present it logically and succinctly to the reader in the following format:

If there is no definition of a unit of complexity in mathematics, then does or can the notion of estimating complexity in mathematics, make any sense or even possible?

Comments (9)

jgill October 15, 2021 at 03:23 #607360
A mathematician might say, "That proof was quite complex". Another might add, "Yes, but elementary!"
Both could be correct.

Complexity of proof is a kind of meta-mathematics idea that most mathematicians wouldn't be interested in pursuing. More likely a computer scientist of some sort.

Beyond that, there is complexity of mathematical specialties. Euclidean geometry would be considered fairly light on complexity as compared with Scheme Mathematics
Shawn October 15, 2021 at 03:51 #607367
Reply to jgill

It sort of strikes me as odd that the only physical units to determine complexity in mathematical computations would be quantum computers with qubits... What do you think?
jgill October 15, 2021 at 03:56 #607371
Quoting Shawn
It sort of strikes me as odd that the only physical units to determine complexity in mathematical computations would be quantum computers with qubits... What do you think?


New to me. Provide a link or two.
I like sushi October 15, 2021 at 04:01 #607372
Reply to Shawn I think you'll find it is cbits for complexity (see Shannon Entropy).
Shawn October 15, 2021 at 04:05 #607374
Reply to jgill

Sorry I can only reference Shor's algorithm as an example of what I am saying, and it ain't that much.
Shawn October 15, 2021 at 04:07 #607375
Reply to I like sushi

I think I see what your getting at information-wise, yet to parametrize for units you would need some operation other than in silicone to estimate a value for a unit of complexity, no?

Otherwise the example of qubits is sufficient to demonstrate the issue?
jgill October 15, 2021 at 04:12 #607376
Reply to Shawn You've gone down the path of algorithmic theory again, which has little to do with a typical mathematical proof. Not my bailiwick.
hanaH October 15, 2021 at 04:51 #607389
Reply to Shawn
How about defining the complexity of a theorem as the length of its shortest proof in some formal system? For each formal system you could have a different unit. Each proof found for that theorem would give an upper bound.

It's my understanding that it's impossible to prove in general that a shortest proof has been found.
Caldwell October 15, 2021 at 05:20 #607401
Quoting Shawn
If there is no definition of a unit of complexity in mathematics, then does or can the notion of estimating complexity in mathematics, make any sense or even possible?

It's not that it wouldn't make any sense, but math calculations are about precision -- how small or large or steep or within the smallest possible error, to the nth degree, or to .oooooooo1 point you can get. You don't talk about how complex it can be.

Don't fall for quotes like "we don't do it cause it's easy, we do it cause it's hard" nonsense.