Initial segments of computable linear orders with additional computable predicates

We study computable linear orders with computable neighborhood and block predicates. In particular, it is proved that there exists a computable linear order with a computable neighborhood predicate, having a Π₁⁰ -initial segment which is isomorphic to no computable order with a computable neighborhood predicate. On the other hand, every Σ₁⁰ -initial segment of such an order has a computable copy enjoying a computable neighborhood predicate. Similar results are stated for computable linear orders with a computable block predicate replacing a neighborhood relation. Moreover, using the results obtained, we give a simpler proof for the Coles–Downey–Khoussainov theorem on the existence of a computable linear order with Π₂⁰ -initial segment, not having a computable copy.     

Computational complexity of logical theories of one successor and another unary function

The first-order logical theory Th\(({\mathbb{N}},x + 1,F(x))\) is proved to be complete for the class ATIME-ALT\((2^{O(n)},O(n))\) when \(F(x) = 2^{x}\), and the same result holds for \(F(x) = c^{x}, x^{c} (c \in {\mathbb{N}}, c \ge 2)\), and F(x) =  tower of x powers of two. The difficult part is the upper bound, which is obtained by using a bounded Ehrenfeucht–Fraïssé game.     

Computability on linear orderings enriched with predicates

Let L be a quasidiscrete linear ordering. We specify some conditions for the existence of a computable presentation for L or for the structure (L, adj), where adj(x, y) is a predicate distinguishing adjacent elements.     

The complete isomorphism class of an operator space

Suppose is an infinite-dimensional operator space and is a positive integer. We prove that for every there exists an operator space such that the formal identity map is a complete isomorphism, is an isometry, and . This provides a non-commutative counterpart to a recent result of W. Johnson and E. Odell.

     

Testing planar pictures for isomorphism in linear time

A planar picture is defined as an embedding of a planar graph in a plane. Two pictures are said to be isoraorphic if one of them can be mapped onto the other by an isotopy of the plane. A linear time algorithm (in the RAM) is constructed that tests two pictures for isomorphism.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Institute im. V. A. Stekolova Akad. Nauk SSSR, Vol. 174, pp. 101–121, 1988.     

Recursive linear orders with recursive successivities

A successivity in a linear order is a pair of elements with no other elements between them. A recursive linear order with recursive successivities $\text{U}$ is recursively categorical if every recursive linear order with recursive successivities isomorphic to $\text{U}$ is in fact recursively isomorphic to $\text{U}$. We characterize those recursive linear orders with recursive successivities that are recursively categorical as precisely those with order type k₁+g₁+k₂+g₂+…+g_n-1+k_n where each k_n is a finite order type, non-empty for i?{2,…,n-1} and each g_i is an order type from among {ω,ω^*,ω+ω^*}∪{k·η:k<ω}.     

Groups with finitely many linear orders

It is proved that there exist orderable groups having exactly 6 and 14 distinct linear orders. For any natural number k, we construct examples of orderable groups on which 2(4k+3) linear orders are defined. Supported by RFFR grant No. 96-01-00088. Translated fromAlgebra i Logika, Vol. 38, No. 2, pp. 176–200, March–April, 1999.     

A Ramsey theorem for partial orders with linear extensions

We prove a Ramsey theorem for finite sets equipped with a partial order and a fixed number of linear orders extending the partial order. This is a common generalization of two recent Ramsey theorems due to Sokić. As a bonus, our proof gives new arguments for these two results.     

Lattices of equational theories are congruence lattices of monoids with one additional unary operation

The problem of characterizing the lattices of equational theories is still unsolved. In this paper it is shown that these lattices are congruence lattices of an algebra whose fundamental operations consist of one monoid operation with right zero and one unary operation.Presented by R. McKenzie.     

Concerning the complexity of deciding isomorphism of block designs

A construction is described to encode an arbitrary graph uniquely as a block design. This demonstrates that describing whether two block designs (without repeated blocks) are isomorphic is polynomial time equivalent to solving graph isomorphism. This result supplies evidence for the claim that isomorphism testing for block designs is a hard subcase of graph isomorphism.     

NP-hardness results for the aggregation of linear orders into median orders

Given a collection Π of individual preferences defined on a same finite set of candidates, we consider the problem of aggregating them into a collective preference minimizing the number of disagreements with respect to Π and verifying some structural properties. We study the complexity of this problem when the individual preferences belong to any set containing linear orders and when the collective preference must verify different properties, for instance transitivity. We show that the considered aggregation problems are NP-hard for different types of collective preferences (including linear orders, acyclic relations, complete preorders, interval orders, semiorders, quasi-orders or weak orders), if the number of individual preferences is sufficiently large.     

Coloring linear orders with Rado's partial order

Let ?_R be the preorder of embeddability between countable linear orders colored with elements of Rado's partial order (a standard example of a wqo which is not a bqo). We show that ?_R has fairly high complexity with respect to Borel reducibility (e.g. if P is a Borel preorder, then P ≤_B ?_R), although its exact classification remains open. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

The proof complexity of linear algebra

We introduce three formal theories of increasing strength for linear algebra in order to study the complexity of the concepts needed to prove the basic theorems of the subject. We give what is apparently the first feasible proofs of the Cayley–Hamilton theorem and other properties of the determinant, and study the propositional proof complexity of matrix identities such as AB=I→BA=I.     

Computational complexity of reconstruction and isomorphism testing for designs and line graphs

Graphs with high symmetry or regularity are the main source for experimentally hard instances of the notoriously difficult graph isomorphism problem. In this paper, we study the computational complexity of isomorphism testing for line graphs of t-(v,k,λ) designs. For this class of highly regular graphs, we obtain a worst-case running time of O(vlogv+O(1)) for bounded parameters t, k, λ.In a first step, our approach makes use of the Babai-Luks algorithm to compute canonical forms of t-designs. In a second step, we show that t-designs can be reconstructed from their line graphs in polynomial-time. The first is algebraic in nature, the second purely combinatorial. For both, profound structural knowledge in design theory is required. Our results extend earlier complexity results about isomorphism testing of graphs generated from Steiner triple systems and block designs.