7

Restrictions on pre-orders You've described that you would like to assert restrictions on a given pre-order: for instance, that specifically $a < b$ rather than merely $a \leqslant b$, so that it would not be compatible with a pre-order in which $a \cong b$ (that is $a \leqslant b$ and $b \leqslant a$). We can achieve this by supplementing the pre-order ...


7

Note that the conditions imply that $T$ is recursive. The construction below shows that apart from that, its complexity can be arbitrarily large. Let $L\subseteq\mathbb N$ be an arbitrary recursive language, and $f\colon\mathbb N\to\mathbb N$ a function such that $x\in L$ is decidable in time $|f(x)|$, and the subgraph $\{(x,y):y<f(x)\}$ is polynomial-...


4

I assume you're talking about maintaining keys, in order, in an $O(N)$-sized array, with $O(\log^2 N)$ amortized worst-case update time. At the beginning how many chunks do I have? I suppose one. At the beginning, you will have one chunk. Ordered file maintenance doesn't make sense for very small arrays. Pick a smallish number (like 64 or 1024), and ...


3

I have an example where $T$ is not total, and is only a pre-order. On the other hand, $S$ is in $\mathbf P$ and $T$ is undecidable, so it is even worse than being not polynomial. The pre-order $S$ is on encodings $\langle M,x\rangle$, where $M$ is the encoding of a Turing Machine, and $x$ is a number of steps in unary. We define $(\langle M,x\rangle, \...


2

I believe A sparse table implementation of priority queues by Alon Itai, Alan G. Konheim, and Michael Rodeh is the source of this method. I haven't read the whole paper, but I believe the reason these details are vaguely described is that more than one method for, eg, expanding the table is given (see pg. 424): One way to increase the size of the ...


2

Leaving the current answer accepted because it's closer to the original question than this, but I've realised the following nice class of almost example where as Denis suggested we drop the restriction that the order be total, so I thought I'd share (not suggesting this is a "better" answer, only that it was easier for me to understand and seems somehow ...


Only top voted, non community-wiki answers of a minimum length are eligible