• Shawn
    13.2k
    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?
  • jgill
    3.8k
    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
    13.2k


    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
    3.8k
    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?Shawn

    New to me. Provide a link or two.
  • I like sushi
    4.8k
    I think you'll find it is cbits for complexity (see Shannon Entropy).
  • Shawn
    13.2k


    Sorry I can only reference Shor's algorithm as an example of what I am saying, and it ain't that much.
  • Shawn
    13.2k


    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
    3.8k
    You've gone down the path of algorithmic theory again, which has little to do with a typical mathematical proof. Not my bailiwick.
  • hanaH
    195

    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
    1.3k
    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?Shawn
    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.
bold
italic
underline
strike
code
quote
ulist
image
url
mention
reveal
youtube
tweet
Add a Comment

Welcome to The Philosophy Forum!

Get involved in philosophical discussions about knowledge, truth, language, consciousness, science, politics, religion, logic and mathematics, art, history, and lots more. No ads, no clutter, and very little agreement — just fascinating conversations.