7 ms·

"That would be the most interesting possibility, Trevisan said, since it would make graph isomorphism the first natural problem to have a quasi-polynomial algor

"That would be the most interesting possibility, Trevisan said, since it would make graph isomorphism the first natural problem to have a quasi-polynomial algorithm but no polynomial algorithm. " "Proving it would amount to solving the P versus NP problem, since it would mean that graph isomorphism separates the problems in P from the NP-complete problems." (exp((log n)^O(1))) Interesting that there could be a much more varied landscape than was previously thought.

mehrdadn 7y ago
One thing that's bothered me ever since I heard about complexity theory is why there is no explanation given as to why polynomial and exponential complexities are given such special status. It's just taken for granted that polynomials and exponential are the 2 classes you care about... with no explanation as to why the rest aren't interesting. EDIT: Edited to clarify, sorry the question was unclear. Thanks for all the replies, but yes, I know the basics :-) I'm not asking about why polynomial complexities themselves are special. Rather, I was trying to ask why we only ever talk about polynomials and exponentials. The only thing that's ever justified is polynomial-time reducibility within a class (which also inherently defines the P class itself). That part is fine. But then once that's established, people suddenly start talking about exponentials. Sorry, but what just happened? There are an infinite number of complexities in between to consider! Why should I suddenly not care about everything in between? Why am I not taught a single algorithm whose complexity is between these? is my question.
- kevinventullo 7y ago
  I think it's just that many natural algorithms happen to have polynomial time complexity, since it's basically the complexity of iterated loops. Same with logarithms.
- dragontamer 7y ago
  Because O(e^x) > O(x^n), for all Integer values of "n". So Polynomial is simply a class that we know is strictly "faster" (well, asymptotically faster) than any exponential function. In practice, I think real-life humans only care for "small polynomials". An algorithm with complexity (x^5000) will be growing too quickly to be used in practice, even if its big-Oh is technically polynomial. Well, I say that, except 3SAT solvers are a thing and that's provably NP-complete. So lots of people bang their heads against the NP-complete problems anyway.
  - mehrdadn 7y ago
    > Because O(e^x) > O(x^n), for all Integer values of "n" No, that just tells me why we make a distinction between exponentials and polynomials, not why we always focus on those two in particular. It's not like there aren't other complexities in between that you can't make the same kind of statement about...
    - dragontamer 7y ago
      Hmmm, I think you're trying to divine a deeper meaning in something that doesn't necessarily exist. Complexity theory itself is a gross estimation on reality and performance. Complexity theory tells you nothing about how fast (or slow) an algorithm is in practice: quicksort typically is faster than merge sort, despite both being O(n * log(n)). Heck, quicksort can be faster than radix sort in many cases. Another case: Bitonic sort is asymptotically slower at O(n * log^2(n)), but Bitonic sort lends itself to parallelism very well, so its "faster" in practice (even if its not work-efficient). So why do people use complexity analysis at all? Its completely irrelevant to determining quicksort vs mergesort vs bitonic sort! Well, simple: because its relatively easy to calculate, and relatively easy to understand. Polynomial time, and Nondeterministic Polynomial time (aka NP-complete) are both "easy" to describe and understand (for a... somewhat interesting definition of easy). At least, in the greater scope of mathematics they're concise and "simple" definitions. ---------- A great number of algorithms in Knuth's "The Art of Computer Programming" are calculated out to the precise number of assembly-language statements executed... including the constant. No "big-O" estimates involved. This deeper analysis is great to read once or twice, but read enough of it and you realize how much harder it is to think about. Complexity theory is far faster to analyze and apply to algorithms, even if its an incomplete picture. As such, emphasis should be on "ease of use" and "convenience" as opposed to any real amounts of practical rigor. ---------- The other issue: is that NP vs P is the great unsolved mathematical problem of our lifetime. So a huge amount of professors introduce the concept of NP vs P so that their students can be ready for a major mathematical debate relevant to the field. ----------- EDIT: In practical optimization, I think most people care about "Linear", "Sublinear", and "Superlinear". For example, the Painter's Algorithm for GPUs is superlinear: O(n * log(n)). But a depth-test based approach to GPU scene painting is linear: O(n). Linear is "good enough" so optimization basically stops there. Any algorithm that visits all data is going to be, at best, linear. So that's why GPU programmers probably are happy with "depth test", because Asymptotically Linear complexity is the best you can reasonably hope for.
- sischoel 7y ago
  The class of polynomial time algorithms is closed for some things, that you often see in algorithms: - If you run two polynomial time algorithms in parallel, the result is a polynomial time algorithm again. - If one operation of a polynomial time algorithm, is calling another polynomial time algorithm, then the result runs in polynomial time again.
  - mehrdadn 7y ago
    By this justification exponentials wouldn't be any more interesting than stuff between exponentials and polynomials either, right? So why we still generally taught both, but only these two? Aren't there an infinite number of complexities above polynomial to worry about? is my point.
    - repsilat 7y ago
      "Exponential" is often colloquial short-hand for EXPTIME, which is closed under some useful operations (because there's an "any polynomial" in the exponent.) For one thing, it's robust to reasonable changes of model, for "No true Scotsman" definitions of "reasonable".
      - mehrdadn 7y ago
        You're talking about closure of EXPTIME under polynomial transformations. You could do similar for quasipolynomial and such; there's nothing about EXPTIME that makes it special in this regard. Edited my comment slightly to hopefully clarify.
    - jules 7y ago
      Exponential is interesting for P=?NP because the naive method for NP problems runs in exponential time.
- ivanbakel 7y ago
  Because polynomial complexity is the measure of what makes a tractable problem [1]. If the question is why - there's no formal reason. Tractability is really just subjective human standards: even high-degree polynomial time is often considered to not enough for a solution to be worthwhile computing. [1][https://en.wikipedia.org/wiki/Cobham%27s_thesis https://en.wikipedia.org/wiki/Cobham%27s_thesis]
  - mehrdadn 7y ago
    Yes, my question was indeed why. At the very least, I would hope for explicit mentions that this is an arbitrary choice when the subject is being taught, and mentions of algorithms with running times between polynomials and exponentials. Otherwise it gives people the wrong impression that there isn't anything in between worth considering, which is misleading and just wrong.
- yorwba 7y ago
  Polynomials are convenient because they allow you to mostly ignore the details of the underlying model of computation. E.g. if you try to simulate a multi-headed Turing machine with a single-headed one, you'll spend a lot of time moving between different positions on the tape, increasing the runtime complexity by a polynomial factor. By considering all polynomials as essentially equivalent, you can choose whichever abstraction you want without having to think too hard about the overhead it adds. That's of course bad if you actually want to implement the fastest algorithm, but it makes proving (and stating) theorems a lot simpler.
  - mehrdadn 7y ago
    Yup this is the justification for why polynomial reductions should define everything within class, but it doesn't seem to justify why we should only focus on the polynomial and exponential classes to begin with, given there are infinitely many classes in between (and beyond exponential). Sorry my question didn't make it clear that's what I was asking about; I edited it to hopefully clarify.
    - skinner_ 7y ago
      Complexity theorists do care about reductions within subexponential time classes, but it's not a great topic for P vs NP focused Complexity Theory 101. And when you do focus on P vs NP, the dichotomy is quite natural because of the https://en.wikipedia.org/wiki/Exponential_time_hypothesis https://en.wikipedia.org/wiki/Exponential_time_hypothesis, the conjecture that a broad class of NP-complete problems are exponential-time.
- jimhefferon 7y ago
  When you start listing algorithms, you see that their speeds fall in a line. There are the log ones, the polys (with n lg n between n and n^2), the exponentials, and higher. So why the distinction between poly and exp? A modern computer runs at about 10 GHz, 10,000 million ticks per second, and there are about 3.16×10^7 seconds in a year. Suppose your problem has size n=100. Then an n^3 algorithm takes 3.17×10^{-12} years. A 2^n algorithm takes 4.02×10^{12} years. The first is perfectly practible, the second is not (its time is longer than the age of the universe).
  - mehrdadn 7y ago
    Thanks! But my question wasn't as basic as this :-) I tried to edit to clarify.
- wolfgke 7y ago
  > One thing that's bothered me ever since I heard about complexity theory is why there is no explanation given as to why polynomial complexities are given such special status. It's just taken for granted that polynomials are the class you care about... with no explanation as to why. The reason is that if we take something more fine-grained than polynomial, whether the runtime is in this class or not can strongly depend on the machine model (e.g. Turing machine, register machine (counter machine, pointer machine, random-access stored-program machine), etc.). On the other hand, for nearly all machine models, one can show that they can be emulated by another machine model with at most a polynomial-time overhead. This is seen as a strong sign that polynomial-time is probably what we are looking for. Another strong sign is that there exist problem classes (NPcomplete, coNPcomplete) to which every problem in NP/coNP can be reduced by a polynomial-time reduction (that such a class exists is IMHO a very surprising result). This is seen as another strong sign that polynomial-time could be a good idea.
  - mehrdadn 7y ago
    > if we take something more fine-grained than polynomial I didn't mean more fine-grained than polynomial. I meant between polynomial and exponential. > On the other hand, for nearly all machine models, one can show that they can be emulated by another machine model with at most a polynomial-time overhead. This is seen as a strong sign that polynomial-time is probably what we are looking for. > Another strong sign is that there exist problem classes (NPcomplete, coNPcomplete) to which every problem in NP/coNP can be reduced by a polynomial-time reduction (that such a class exists is IMHO a very surprising result). This is seen as another strong sign that polynomial-time could be a good idea. These just say why we care about polynomial-time reducibility as a means for specifying a class. It doesn't say why we only look at polynomial and exponentials classes though, which is what i'm saying. There are infinitely many classes in between. Why just focus on these two?
    - gchpaco 7y ago
      There are only two "natural" problem classes known that are not either definitely in P or definitely in NP, and this article concerns one of them. (The other is integer factorization / discrete logs). And I'm not sure anybody believes there are any natural problems that are inherently in this in between state.
- MaxBarraclough 7y ago
  Good lord! Reply after reply after reply that simply refuse to speak to the question you asked! You're quite right that complexity theory takes us to a hierarchy far richer than simply polynomial and exponentiation [0]. Your question about the emphasis on those two in particular, is a good one. Might be worth submitting on cs.stackexchange.com as a 'soft question'. [0] https://en.wikipedia.org/wiki/Time_complexity#Table_of_common_time_complexities https://en.wikipedia.org/wiki/Time_complexity#Table_of_commo...
  - mehrdadn 7y ago
    Thanks, yeah, might do that at some point. :)
- xorand 7y ago
  Well in mathematics there is a somewhat similar phenomenon concerning the growth of finitely generated groups. If you have a finitely generated group, pick a generating set as an alphabet and a natural n, then ask how many elements of the group you can build by using only words of length at most n. This is the growth function, whose growth does not change if you pick another generating set. See [1] the Tits alternative which implies that if your group is linear (huh) then the growth function is either polynomial or exponential. Then there is a result by Gromov [2] which says that if the growth is polynomial then the group is virtually nilpotent. There was a long standing question if there exist finitely generated groups with an intermediate growth and the first example was found [3]. So it's not interesting until it becomes interesting due to a newly discovered fact. [1] https://en.wikipedia.org/wiki/Tits_alternative https://en.wikipedia.org/wiki/Tits_alternative [2] https://en.wikipedia.org/wiki/Gromov%27s_theorem_on_groups_of_polynomial_growth https://en.wikipedia.org/wiki/Gromov%27s_theorem_on_groups_o... [3] https://en.wikipedia.org/wiki/Grigorchuk_group https://en.wikipedia.org/wiki/Grigorchuk_group
  - mehrdadn 7y ago
    Wow that's definitely interesting :-) thanks for sharing this! Makes you wonder if there's a deeper connection between these two areas!
- abdullahkhalids 7y ago
  I think the answer is much more trivial than you think. Polynomials and exponential complexities are given such special status simply because when we start classifying "natural" problems, many of them either fall into one of these classes, and not many in the intermediate classes. If they fell into polynomial and sub-exponential time, computer science text books would have chapters dedicated to these two instead. At the end of the day CS is used to make building technology easier and so computer scientists naturally interested in "natural" problems and not artificially designed problems. Now, why "natural" problems so easily fall into these two categories and not others is a different mystery and not what you asked.
  - repsilat 7y ago
    It's also a robust distinction because polymomials are closed under addition, multiplication and composition. Converting an algorithm from a Turing machine to a random-access model will often give you a polynomial speedup, but not an exponential one, so "polynomial time" means the same for both. If you have a problem A, and a polynomial reduction from A to B, and a polynomial algorithm for B, you have a polynomial algorithm for A. Sometimes algorithms can be polynomial but intractable (or even exponential but practical for some real cases), but it's less "neat" or clean to reason about those things. (Very useful, though, just more done outside the academy.) As for things that aren't polynomial, I guess exponential things just happen to be the most common kind? Not sure myself why "pseudo-polynomial" bounds aren't more common.
- nwallin 7y ago
  > Why am I not taught a single algorithm whose complexity is between these? is my question. Despite the fact that there are infinitely many such algorithms, it's a very small infinity, where infinity is approximately equal to 2. There are the algorithms for factoring large numbers, and the graph isomorphism problem. All these algorithms are a lot of work to implement with lots of fiddly bits, and it's very difficult to show precisely what their complexity is. (unless you get one of the fiddly bits wrong, in which case it's easy to show that they're either polynomial or exponential time) So they're generally bad teaching examples. If the professor give it to them as a homework assignment, they'll fail it, and if the professor goes through the algorithm and the proof in class it will be an exercise in "But I don't understand the step here where you just waved your hands and moved on to the next step." It's like asking why we don't care about the stuff between Mars and Jupiter; it's not that there's nothing there, it's that they're less interesting than Mars or Jupiter and you can't do Useful Science on them with undergraduate time/money commitments.
  - mehrdadn 7y ago
    > Despite the fact that there are infinitely many such algorithms, it's a very small infinity, where infinity is approximately equal to 2. There are the algorithms for factoring large numbers, and the graph isomorphism problem. I assume you mean "interesting" ones? Since they could just show a program that counts up to n^log(n) and voila, you have a super-polynomial sub-exponential algorithm. In which case... I still don't think it's just algorithms for these problems? https://en.wikipedia.org/wiki/Adleman%E2%80%93Pomerance%E2%80%93Rumely_primality_test https://en.wikipedia.org/wiki/Adleman%E2%80%93Pomerance%E2%8... But if they're all still complicated, and this is why they're not taught, then I feel like I'd have appreciated being told this at least...
    - deleted 7y ago
      [deleted]
- svat 7y ago
  You may like reading Scott Aaronson's P vs NP survey (2017), which may answer some of your questions about complexity theory: https://www.scottaaronson.com/papers/pnp.pdf https://www.scottaaronson.com/papers/pnp.pdf In particular, the section relevant to your question is "1.2.2 The Polynomial-Time Objection" on page 7, quoted in full below: > Objection: But why should we draw the border of efficiency at the polynomial functions, as opposed to any other class of functions—for example, functions upper-bounded by n^2, or functions of the form n^((log n)^c) (called quasipolynomial functions)? > Response: There’s a good theoretical answer to this: it’s because polynomials are the smallest class of functions that contains the linear functions, and that’s closed under basic operations like addition, multiplication, and composition. For this reason, they’re the smallest class that ensures that we can compose “efficient algorithms” a constant number of times, and still get an algorithm that’s efficient overall. For the same reason, polynomials are also the smallest class that ensures that our “set of efficiently solvable problems” is independent of the low-level details of the machine model. > Having said that, much of algorithms research is about lowering the order of the polynomial, for problems already known to be in P, and theoretical computer scientists do use looser notions like quasipolynomial time whenever they’re needed. To add a couple of points of my own: - We need to consider at least polynomial functions, for the closed-ness reason (though in practice the exponent is usually small), and superpolynomial functions (in the theoretical/asympotic sense, slower than any polynomial, even n^100000 or whatever!) are already slow enough not to be considered efficient. For that matter do you learn any single exponential algorithm in (say) an undergraduate course? If you're in an area where exponential algorithms are of interest though, then it's not actually unusual to study sub-exponential (and superpolynomial) ones, as those are the most efficient we have. * There are not many "simple" superpolynomial subexponential algorithms, suitable for a typical first course. Factoring could be taught though, if the students are all interested in number theory I guess. When I took a course on "algebra and computation" (problems in group theory etc), we did encounter quite a few such algorithms.
  - mehrdadn 7y ago
    > Scott Aaronson's P vs NP survey Thanks for the link, but again, it only explains why polynomials are interesting, not why we don't care about things bete > For that matter do you learn any single exponential algorithm in (say) an undergraduate course? Fibonacci? And basically brute-force solution to pretty much any problem they give you in a first course? > There are not many "simple" superpolynomial subexponential algorithms, suitable for a typical first course. Yeah I'm getting to the conclusion this is the crux of it. It'd be nice if they at least mentioned this is why?
- gnull 7y ago
  That's exactly how I felt about polynomial time definition when I was just starting to study complexity theory. Now, after a two year complexity-focused master program, I realized a few things which changed the way I perceive it: 1. P is a roughly approximate definition of «feasible» problems. P doesn't perfectly capture problems we intuitively understand as feasible (e.g, P includes problems which are solved in O(n^10000) time), but it is good in other respects: its definition is independent of computation model (but the model has to be able to simulate a Turing machine with at most polynomial slowdown, which is true for all reasonable models); P has complete problems; P is closed under many ways of combining algorithms (e.g. if you run a poly-time algorithm poly times, what you get is also a poly-time algorithm). So P isn't perfect way to define feasible problems, but it's good enough (or maybe the best we have?). There may exist other ways to formalize feasible computations, which could fix P's drawbacks. Maybe complexity theorists will come up with one later, when they get a better understanding of computations. But until then, they work with what they've got. 2. Even if you don't buy all this «feasibility» interpretation, P will still make perfect sense for theory. Especially, when you ask questions about its relation to other classes. It is natural for computer scientists to consider variations of some computation model and try to understand which of those variations are stronger and how much stronger they are. For example, randomized and nondeterministic Turing machines are variations of usual deterministic Turing machine (DTM). But the former two have their own unique superpowers, which are randomness and nondeterminism. But how powerful these superpowers are? Can a DTM provided with such a superpower solve more problems? And if so, can we compensate the DTM's lack of superpower by providing it more running time? How much time would suffice for that? In these terms we can say, that P-vs-NP question actually asks whether polynomial-time DTM's lack of nondeterminism can be compensated by allowing it to run poly(n) times longer. Similarly, if you ask the same question but with «randomness» instead of «nontereminism», you will get another famous problem of P-vs-ZPP (or P-vs-BPP, depending on your definition of randomness). Computer scientists asked similar questions for models other than Turing machine, and successfully answered them. For example, for finite automatons we already know how many extra states we need to go from nondeterministic to deterministic one. Similarly, for communication complexity we know something about the relation between nondeterministic, deterministic, and randomized complexity. EDIT: Ooops, I replied to the original version of your post, before you clarified what you meant.

mehrdadn 7y ago

One thing that's bothered me ever since I heard about complexity theory is why there is no explanation given as to why polynomial and exponential complexities are given such special status. It's just taken for granted that polynomials and exponential are the 2 classes you care about... with no explanation as to why the rest aren't interesting. EDIT: Edited to clarify, sorry the question was unclear. Thanks for all the replies, but yes, I know the basics :-) I'm not asking about why polynomial complexities themselves are special. Rather, I was trying to ask why we only ever talk about polynomials and exponentials. The only thing that's ever justified is polynomial-time reducibility within a class (which also inherently defines the P class itself). That part is fine. But then once that's established, people suddenly start talking about exponentials. Sorry, but what just happened? There are an infinite number of complexities in between to consider! Why should I suddenly not care about everything in between? Why am I not taught a single algorithm whose complexity is between these? is my question.

kevinventullo 7y ago
I think it's just that many natural algorithms happen to have polynomial time complexity, since it's basically the complexity of iterated loops. Same with logarithms.
dragontamer 7y ago
Because O(e^x) > O(x^n), for all Integer values of "n". So Polynomial is simply a class that we know is strictly "faster" (well, asymptotically faster) than any exponential function. In practice, I think real-life humans only care for "small polynomials". An algorithm with complexity (x^5000) will be growing too quickly to be used in practice, even if its big-Oh is technically polynomial. Well, I say that, except 3SAT solvers are a thing and that's provably NP-complete. So lots of people bang their heads against the NP-complete problems anyway.
- mehrdadn 7y ago
  > Because O(e^x) > O(x^n), for all Integer values of "n" No, that just tells me why we make a distinction between exponentials and polynomials, not why we always focus on those two in particular. It's not like there aren't other complexities in between that you can't make the same kind of statement about...
  - dragontamer 7y ago
    Hmmm, I think you're trying to divine a deeper meaning in something that doesn't necessarily exist. Complexity theory itself is a gross estimation on reality and performance. Complexity theory tells you nothing about how fast (or slow) an algorithm is in practice: quicksort typically is faster than merge sort, despite both being O(n * log(n)). Heck, quicksort can be faster than radix sort in many cases. Another case: Bitonic sort is asymptotically slower at O(n * log^2(n)), but Bitonic sort lends itself to parallelism very well, so its "faster" in practice (even if its not work-efficient). So why do people use complexity analysis at all? Its completely irrelevant to determining quicksort vs mergesort vs bitonic sort! Well, simple: because its relatively easy to calculate, and relatively easy to understand. Polynomial time, and Nondeterministic Polynomial time (aka NP-complete) are both "easy" to describe and understand (for a... somewhat interesting definition of easy). At least, in the greater scope of mathematics they're concise and "simple" definitions. ---------- A great number of algorithms in Knuth's "The Art of Computer Programming" are calculated out to the precise number of assembly-language statements executed... including the constant. No "big-O" estimates involved. This deeper analysis is great to read once or twice, but read enough of it and you realize how much harder it is to think about. Complexity theory is far faster to analyze and apply to algorithms, even if its an incomplete picture. As such, emphasis should be on "ease of use" and "convenience" as opposed to any real amounts of practical rigor. ---------- The other issue: is that NP vs P is the great unsolved mathematical problem of our lifetime. So a huge amount of professors introduce the concept of NP vs P so that their students can be ready for a major mathematical debate relevant to the field. ----------- EDIT: In practical optimization, I think most people care about "Linear", "Sublinear", and "Superlinear". For example, the Painter's Algorithm for GPUs is superlinear: O(n * log(n)). But a depth-test based approach to GPU scene painting is linear: O(n). Linear is "good enough" so optimization basically stops there. Any algorithm that visits all data is going to be, at best, linear. So that's why GPU programmers probably are happy with "depth test", because Asymptotically Linear complexity is the best you can reasonably hope for.
sischoel 7y ago
The class of polynomial time algorithms is closed for some things, that you often see in algorithms: - If you run two polynomial time algorithms in parallel, the result is a polynomial time algorithm again. - If one operation of a polynomial time algorithm, is calling another polynomial time algorithm, then the result runs in polynomial time again.
- mehrdadn 7y ago
  By this justification exponentials wouldn't be any more interesting than stuff between exponentials and polynomials either, right? So why we still generally taught both, but only these two? Aren't there an infinite number of complexities above polynomial to worry about? is my point.
  - repsilat 7y ago
    "Exponential" is often colloquial short-hand for EXPTIME, which is closed under some useful operations (because there's an "any polynomial" in the exponent.) For one thing, it's robust to reasonable changes of model, for "No true Scotsman" definitions of "reasonable".
    - mehrdadn 7y ago
      You're talking about closure of EXPTIME under polynomial transformations. You could do similar for quasipolynomial and such; there's nothing about EXPTIME that makes it special in this regard. Edited my comment slightly to hopefully clarify.
  - jules 7y ago
    Exponential is interesting for P=?NP because the naive method for NP problems runs in exponential time.
ivanbakel 7y ago
Because polynomial complexity is the measure of what makes a tractable problem [1]. If the question is why - there's no formal reason. Tractability is really just subjective human standards: even high-degree polynomial time is often considered to not enough for a solution to be worthwhile computing. [1][https://en.wikipedia.org/wiki/Cobham%27s_thesis https://en.wikipedia.org/wiki/Cobham%27s_thesis]
- mehrdadn 7y ago
  Yes, my question was indeed why. At the very least, I would hope for explicit mentions that this is an arbitrary choice when the subject is being taught, and mentions of algorithms with running times between polynomials and exponentials. Otherwise it gives people the wrong impression that there isn't anything in between worth considering, which is misleading and just wrong.
yorwba 7y ago
Polynomials are convenient because they allow you to mostly ignore the details of the underlying model of computation. E.g. if you try to simulate a multi-headed Turing machine with a single-headed one, you'll spend a lot of time moving between different positions on the tape, increasing the runtime complexity by a polynomial factor. By considering all polynomials as essentially equivalent, you can choose whichever abstraction you want without having to think too hard about the overhead it adds. That's of course bad if you actually want to implement the fastest algorithm, but it makes proving (and stating) theorems a lot simpler.
- mehrdadn 7y ago
  Yup this is the justification for why polynomial reductions should define everything within class, but it doesn't seem to justify why we should only focus on the polynomial and exponential classes to begin with, given there are infinitely many classes in between (and beyond exponential). Sorry my question didn't make it clear that's what I was asking about; I edited it to hopefully clarify.
  - skinner_ 7y ago
    Complexity theorists do care about reductions within subexponential time classes, but it's not a great topic for P vs NP focused Complexity Theory 101. And when you do focus on P vs NP, the dichotomy is quite natural because of the https://en.wikipedia.org/wiki/Exponential_time_hypothesis https://en.wikipedia.org/wiki/Exponential_time_hypothesis, the conjecture that a broad class of NP-complete problems are exponential-time.
jimhefferon 7y ago
When you start listing algorithms, you see that their speeds fall in a line. There are the log ones, the polys (with n lg n between n and n^2), the exponentials, and higher. So why the distinction between poly and exp? A modern computer runs at about 10 GHz, 10,000 million ticks per second, and there are about 3.16×10^7 seconds in a year. Suppose your problem has size n=100. Then an n^3 algorithm takes 3.17×10^{-12} years. A 2^n algorithm takes 4.02×10^{12} years. The first is perfectly practible, the second is not (its time is longer than the age of the universe).
- mehrdadn 7y ago
  Thanks! But my question wasn't as basic as this :-) I tried to edit to clarify.
wolfgke 7y ago
> One thing that's bothered me ever since I heard about complexity theory is why there is no explanation given as to why polynomial complexities are given such special status. It's just taken for granted that polynomials are the class you care about... with no explanation as to why. The reason is that if we take something more fine-grained than polynomial, whether the runtime is in this class or not can strongly depend on the machine model (e.g. Turing machine, register machine (counter machine, pointer machine, random-access stored-program machine), etc.). On the other hand, for nearly all machine models, one can show that they can be emulated by another machine model with at most a polynomial-time overhead. This is seen as a strong sign that polynomial-time is probably what we are looking for. Another strong sign is that there exist problem classes (NPcomplete, coNPcomplete) to which every problem in NP/coNP can be reduced by a polynomial-time reduction (that such a class exists is IMHO a very surprising result). This is seen as another strong sign that polynomial-time could be a good idea.
- mehrdadn 7y ago
  > if we take something more fine-grained than polynomial I didn't mean more fine-grained than polynomial. I meant between polynomial and exponential. > On the other hand, for nearly all machine models, one can show that they can be emulated by another machine model with at most a polynomial-time overhead. This is seen as a strong sign that polynomial-time is probably what we are looking for. > Another strong sign is that there exist problem classes (NPcomplete, coNPcomplete) to which every problem in NP/coNP can be reduced by a polynomial-time reduction (that such a class exists is IMHO a very surprising result). This is seen as another strong sign that polynomial-time could be a good idea. These just say why we care about polynomial-time reducibility as a means for specifying a class. It doesn't say why we only look at polynomial and exponentials classes though, which is what i'm saying. There are infinitely many classes in between. Why just focus on these two?
  - gchpaco 7y ago
    There are only two "natural" problem classes known that are not either definitely in P or definitely in NP, and this article concerns one of them. (The other is integer factorization / discrete logs). And I'm not sure anybody believes there are any natural problems that are inherently in this in between state.
MaxBarraclough 7y ago
Good lord! Reply after reply after reply that simply refuse to speak to the question you asked! You're quite right that complexity theory takes us to a hierarchy far richer than simply polynomial and exponentiation [0]. Your question about the emphasis on those two in particular, is a good one. Might be worth submitting on cs.stackexchange.com as a 'soft question'. [0] https://en.wikipedia.org/wiki/Time_complexity#Table_of_common_time_complexities https://en.wikipedia.org/wiki/Time_complexity#Table_of_commo...
- mehrdadn 7y ago
  Thanks, yeah, might do that at some point. :)
xorand 7y ago
Well in mathematics there is a somewhat similar phenomenon concerning the growth of finitely generated groups. If you have a finitely generated group, pick a generating set as an alphabet and a natural n, then ask how many elements of the group you can build by using only words of length at most n. This is the growth function, whose growth does not change if you pick another generating set. See [1] the Tits alternative which implies that if your group is linear (huh) then the growth function is either polynomial or exponential. Then there is a result by Gromov [2] which says that if the growth is polynomial then the group is virtually nilpotent. There was a long standing question if there exist finitely generated groups with an intermediate growth and the first example was found [3]. So it's not interesting until it becomes interesting due to a newly discovered fact. [1] https://en.wikipedia.org/wiki/Tits_alternative https://en.wikipedia.org/wiki/Tits_alternative [2] https://en.wikipedia.org/wiki/Gromov%27s_theorem_on_groups_of_polynomial_growth https://en.wikipedia.org/wiki/Gromov%27s_theorem_on_groups_o... [3] https://en.wikipedia.org/wiki/Grigorchuk_group https://en.wikipedia.org/wiki/Grigorchuk_group
- mehrdadn 7y ago
  Wow that's definitely interesting :-) thanks for sharing this! Makes you wonder if there's a deeper connection between these two areas!
abdullahkhalids 7y ago
I think the answer is much more trivial than you think. Polynomials and exponential complexities are given such special status simply because when we start classifying "natural" problems, many of them either fall into one of these classes, and not many in the intermediate classes. If they fell into polynomial and sub-exponential time, computer science text books would have chapters dedicated to these two instead. At the end of the day CS is used to make building technology easier and so computer scientists naturally interested in "natural" problems and not artificially designed problems. Now, why "natural" problems so easily fall into these two categories and not others is a different mystery and not what you asked.
- repsilat 7y ago
  It's also a robust distinction because polymomials are closed under addition, multiplication and composition. Converting an algorithm from a Turing machine to a random-access model will often give you a polynomial speedup, but not an exponential one, so "polynomial time" means the same for both. If you have a problem A, and a polynomial reduction from A to B, and a polynomial algorithm for B, you have a polynomial algorithm for A. Sometimes algorithms can be polynomial but intractable (or even exponential but practical for some real cases), but it's less "neat" or clean to reason about those things. (Very useful, though, just more done outside the academy.) As for things that aren't polynomial, I guess exponential things just happen to be the most common kind? Not sure myself why "pseudo-polynomial" bounds aren't more common.
nwallin 7y ago
> Why am I not taught a single algorithm whose complexity is between these? is my question. Despite the fact that there are infinitely many such algorithms, it's a very small infinity, where infinity is approximately equal to 2. There are the algorithms for factoring large numbers, and the graph isomorphism problem. All these algorithms are a lot of work to implement with lots of fiddly bits, and it's very difficult to show precisely what their complexity is. (unless you get one of the fiddly bits wrong, in which case it's easy to show that they're either polynomial or exponential time) So they're generally bad teaching examples. If the professor give it to them as a homework assignment, they'll fail it, and if the professor goes through the algorithm and the proof in class it will be an exercise in "But I don't understand the step here where you just waved your hands and moved on to the next step." It's like asking why we don't care about the stuff between Mars and Jupiter; it's not that there's nothing there, it's that they're less interesting than Mars or Jupiter and you can't do Useful Science on them with undergraduate time/money commitments.
- mehrdadn 7y ago
  > Despite the fact that there are infinitely many such algorithms, it's a very small infinity, where infinity is approximately equal to 2. There are the algorithms for factoring large numbers, and the graph isomorphism problem. I assume you mean "interesting" ones? Since they could just show a program that counts up to n^log(n) and voila, you have a super-polynomial sub-exponential algorithm. In which case... I still don't think it's just algorithms for these problems? https://en.wikipedia.org/wiki/Adleman%E2%80%93Pomerance%E2%80%93Rumely_primality_test https://en.wikipedia.org/wiki/Adleman%E2%80%93Pomerance%E2%8... But if they're all still complicated, and this is why they're not taught, then I feel like I'd have appreciated being told this at least...
  - deleted 7y ago
    [deleted]
svat 7y ago
You may like reading Scott Aaronson's P vs NP survey (2017), which may answer some of your questions about complexity theory: https://www.scottaaronson.com/papers/pnp.pdf https://www.scottaaronson.com/papers/pnp.pdf In particular, the section relevant to your question is "1.2.2 The Polynomial-Time Objection" on page 7, quoted in full below: > Objection: But why should we draw the border of efficiency at the polynomial functions, as opposed to any other class of functions—for example, functions upper-bounded by n^2, or functions of the form n^((log n)^c) (called quasipolynomial functions)? > Response: There’s a good theoretical answer to this: it’s because polynomials are the smallest class of functions that contains the linear functions, and that’s closed under basic operations like addition, multiplication, and composition. For this reason, they’re the smallest class that ensures that we can compose “efficient algorithms” a constant number of times, and still get an algorithm that’s efficient overall. For the same reason, polynomials are also the smallest class that ensures that our “set of efficiently solvable problems” is independent of the low-level details of the machine model. > Having said that, much of algorithms research is about lowering the order of the polynomial, for problems already known to be in P, and theoretical computer scientists do use looser notions like quasipolynomial time whenever they’re needed. To add a couple of points of my own: - We need to consider at least polynomial functions, for the closed-ness reason (though in practice the exponent is usually small), and superpolynomial functions (in the theoretical/asympotic sense, slower than any polynomial, even n^100000 or whatever!) are already slow enough not to be considered efficient. For that matter do you learn any single exponential algorithm in (say) an undergraduate course? If you're in an area where exponential algorithms are of interest though, then it's not actually unusual to study sub-exponential (and superpolynomial) ones, as those are the most efficient we have. * There are not many "simple" superpolynomial subexponential algorithms, suitable for a typical first course. Factoring could be taught though, if the students are all interested in number theory I guess. When I took a course on "algebra and computation" (problems in group theory etc), we did encounter quite a few such algorithms.
- mehrdadn 7y ago
  > Scott Aaronson's P vs NP survey Thanks for the link, but again, it only explains why polynomials are interesting, not why we don't care about things bete > For that matter do you learn any single exponential algorithm in (say) an undergraduate course? Fibonacci? And basically brute-force solution to pretty much any problem they give you in a first course? > There are not many "simple" superpolynomial subexponential algorithms, suitable for a typical first course. Yeah I'm getting to the conclusion this is the crux of it. It'd be nice if they at least mentioned this is why?
gnull 7y ago
That's exactly how I felt about polynomial time definition when I was just starting to study complexity theory. Now, after a two year complexity-focused master program, I realized a few things which changed the way I perceive it: 1. P is a roughly approximate definition of «feasible» problems. P doesn't perfectly capture problems we intuitively understand as feasible (e.g, P includes problems which are solved in O(n^10000) time), but it is good in other respects: its definition is independent of computation model (but the model has to be able to simulate a Turing machine with at most polynomial slowdown, which is true for all reasonable models); P has complete problems; P is closed under many ways of combining algorithms (e.g. if you run a poly-time algorithm poly times, what you get is also a poly-time algorithm). So P isn't perfect way to define feasible problems, but it's good enough (or maybe the best we have?). There may exist other ways to formalize feasible computations, which could fix P's drawbacks. Maybe complexity theorists will come up with one later, when they get a better understanding of computations. But until then, they work with what they've got. 2. Even if you don't buy all this «feasibility» interpretation, P will still make perfect sense for theory. Especially, when you ask questions about its relation to other classes. It is natural for computer scientists to consider variations of some computation model and try to understand which of those variations are stronger and how much stronger they are. For example, randomized and nondeterministic Turing machines are variations of usual deterministic Turing machine (DTM). But the former two have their own unique superpowers, which are randomness and nondeterminism. But how powerful these superpowers are? Can a DTM provided with such a superpower solve more problems? And if so, can we compensate the DTM's lack of superpower by providing it more running time? How much time would suffice for that? In these terms we can say, that P-vs-NP question actually asks whether polynomial-time DTM's lack of nondeterminism can be compensated by allowing it to run poly(n) times longer. Similarly, if you ask the same question but with «randomness» instead of «nontereminism», you will get another famous problem of P-vs-ZPP (or P-vs-BPP, depending on your definition of randomness). Computer scientists asked similar questions for models other than Turing machine, and successfully answered them. For example, for finite automatons we already know how many extra states we need to go from nondeterministic to deterministic one. Similarly, for communication complexity we know something about the relation between nondeterministic, deterministic, and randomized complexity. EDIT: Ooops, I replied to the original version of your post, before you clarified what you meant.