I have stumbled upon this idea of "algebraic complexity" and I couldn't really find what it is and how it is calculated. For instance: the algebraic complexity of Graham Scan (https://en.wikipedia.org/wiki/Graham_scan) is : second grade polynomials.

Now, another question could sound something similar to this:

Given a triangle ABC, with: A = (xA,yA), B = (xB,yB), C = (xC,yC).¸Let there be P = (xP,yP), Q = (xQ,yQ) other two distinct points in plane. What's the algebraic complexity for:

[?]Deciding if PQ is parallel with AB, AC or BC.

Any ideas?

  • 1
    $\begingroup$ @Vasile Turcu I checked the article you linked. I am good aware of Graham Scan. Not clear at all is the algebraic complexity term. The wiki article does not include the term. Also quick googling gives only few links. You might get better help/answers if you post a link for the general concept here. It might be the complexity of the base function (for Grahmas scan calcuating the cross product) which you have to do n*log(n) times (the runtime complexity of Grahams scan). You could see a cross product somehow as a problem complex as a second grade polynomial. $\endgroup$ – Jan Hackenberg Jan 30 '17 at 16:24
  • $\begingroup$ I only ask this because I see that the question has been migrated from scicomp.stackexchange which is intended for scientist in general. "Could you confirm that you are not talking about just plain old asymptotic notation / analysis which most computer scientist would have already known?" $\endgroup$ – Apiwat Chantawibul Jan 30 '17 at 18:13
  • 2
    $\begingroup$ Well, then in quote "algebraic complexity" is an unfamiliar name to me then. I might not be representative of community, but at least I agree with @Jan Hackenberg that it would really help to link/give your definition "algebraic complexity" here. $\endgroup$ – Apiwat Chantawibul Jan 30 '17 at 18:20
  • 1
    $\begingroup$ @Billiska As much as I would like to, I can't, since this concept I got from one of my past courses I attended. In my native language, the idea was called "complexitate algebrica", hence "algebraic complexity" and I don't have any further information on it than the ones I already posted. $\endgroup$ – Vasile Turcu Jan 30 '17 at 18:37
  • 1
    $\begingroup$ @VasileTurcu "complexitate algebrica" (with quotes) gets exactly four hits on Google for me. :-( $\endgroup$ – David Richerby Jan 30 '17 at 18:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.