Let $\ \mathbf N = \{1\ 2\ \ldots\}\ $ be the set of natural numbers. Let $\ f : \mathbf N\rightarrow\mathbf N\ $ be an arbitrary function, and $\ \forall_{n\in\mathbf N}\, F(n)\ :=\ \max_{k = 1\ldots n}\, f(k)$.

Let's assume that, with respect to a fixed universal Turing machine, there exists at least one algorithm which computes $\ f,\ $ and let $\ ||f||_A(n)\ $ be the number of Turing operations which compute $\ f(n)\ $ by algorithm $\ A$.

By a polynomial $\ \mathbf N\rightarrow\mathbf N\ $ I mean a function which differs from a (true real) polynomial by less then 1 for almost all natural numbers $\ n\in\mathbf N$.


DEFINITION 1   Function $\ f\ $ is called a fast counter $\ \Leftarrow:\Rightarrow\ $ there exists an algorithm $\ A\ $ and a polynomial $\ p : \mathbf N\rightarrow \mathbf N\ $ such that

$$\forall_{n\in\mathbf N}\ \ ||f||_A(n)\ \le\ \frac{p(n)}{n!}\cdot F(n) $$

DEFINITION 2   Function $\ f\ $ is called a slow counter $\ \Leftarrow:\Rightarrow\ $ for every algorithm $\ A\ $ there exists polynomial $\ q : \mathbf N\rightarrow \mathbf N\ $

$$\forall_{n\in\mathbf N}\ \ ||f||_A(n)\ \ge\ \frac{F(n)}{n!\cdot q(n)}$$

DEFINITION 3   Function $\ f\ $ is called an algorithmic counter $\ \Leftarrow:\Rightarrow\ \ f\ $ is both a fast and a slow counter.

QUESTION   Let $\ pos(n)\ $ be the number of all partial orders in the integer interval $\ \{0\ \ldots\ n\!-\!1\}.\ $ Is function $\ pos\ $ an algorithmic counter?

A similar question holds for the number of quasi-orders (i.e. of topologies).

  • 1
    $\begingroup$ Am I right in thinking that this is simply the questions "how fast does the function sending $n$ to the number of partial orders on $\{1,2,...,n\}$ grow?" and "how fast does the function sending $n$ to the number of topologies on $\{1,2,...,n\}$ grow? All this Turing machine stuff must be irrelevant because these functions are trivially bounded by things like $2^{2^n}$ and hence there is no issue with computability. So now you should just work out the answers for $n=1,2,3,4$ and then look up the sequence in OEIS (or just google) and there's your answer, and you can translate it at leisure. $\endgroup$ – znt Sep 18 '16 at 20:38
  • $\begingroup$ @znt -- I disagree. Oh, well... $\endgroup$ – Włodzimierz Holsztyński Sep 18 '16 at 20:52
  • 1
    $\begingroup$ I assume that, in the definition of $F$, the maximum should be over $k=1,2,\dots,n$. In particular, if $f$ is non-decreasing (as in the question at the end), then $F=f$. $\endgroup$ – Andreas Blass Sep 18 '16 at 23:32
  • 1
    $\begingroup$ I agree with znt in the sense that there are many prerequisites to solving this question that you have not mentioned or addressed. Is this because you tried to find the answers and couldn't? (1) What is the best-known algorithm for computing $pos$? (And to be clear, is $pos$ the same as oeis.org/A001035 ?) (2) What are the known upper bounds on the growth rate of $pos$? (3) What are the known lower bounds on the growth rate of $pos$? $\endgroup$ – usul Sep 19 '16 at 2:33
  • 1
    $\begingroup$ I think that this problem is currently intractable. It is known that $\mathrm{pos}(n) = 2^{\frac{n^2}{4}+o(n^2)}$. (More accurate estimates are known but are irrelevant here.) It would be a huge breakthrough to know whether $\mathrm{pos}(n)$ can be computed in time $2^{n^{2-\varepsilon}}$ for some $\varepsilon>0$. $\endgroup$ – Richard Stanley Sep 19 '16 at 17:04

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.