The problem of when a recursive graph has a recursive k-coloring has been extensively studied by Bean, Schmerl, Kierstead, Remmel, and others. In this paper, we study the polynomial time analogue of that problem. We develop a number of negative and positive results about colorings of polynomial time graphs. For example, we show that for any recursive graph G and for any k, there is a polynomial time graph G′ whose vertex set is {0,1}* such that there is an effective (...) degree preserving correspondence between the set of k-colorings of G and the set of k-colorings of G′ and hence there are many examples of k-colorable polynomial time graphs with no recursive k-colorings. Moreover, even though every connected 2-colorable recursive graph is recursively 2-colorable, there are connected 2-colorable polynomial time graphs which have no primitive recursive 2-coloring. We also give some sufficient conditions which will guarantee that a polynomial time graph has a polynomial time or exponential time coloring. (shrink)

We give resource bounded versions of the Completeness Theorem for propositional and predicate logic. For example, it is well known that every computable consistent propositional theory has a computable complete consistent extension. We show that, when length is measured relative to the binary representation of natural numbers and formulas, every polynomial time decidable propositional theory has an exponential time (EXPTIME) complete consistent extension whereas there is a nondeterministic polynomial time (NP) decidable theory which has no polynomial time complete consistent extension (...) when length is measured relative to the binary representation of natural numbers and formulas. It is well known that a propositional theory is axiomatizable (respectively decidable) if and only if it may be represented as the set of infinite paths through a computable tree (respectively a computable tree with no dead ends). We show that any polynomial time decidable theory may be represented as the set of paths through a polynomial time decidable tree. On the other hand, the statement that every polynomial time decidable, relative to the tally representation of natural numbers and formulas, is equivalent to P = NP. For predicate logic, we develop a complexity theoretic version of the Henkin construction to prove a complexity theoretic version of the Completeness Theorem. Our results imply that that any polynomial space decidable theory △ possesses a polynomial space computable model which is exponential space decidable and thus △ has an exponential space complete consistent extension. Similar results are obtained for other notions of complexity. (shrink)

The survey contains a detailed discussion of methods and results in the new emerging area of online “punctual” structure theory. We also state several open problems.

We develop a theory of LOGSPACE structures and apply it to construct a number of examples of Abelian Groups which have LOGSPACE presentations. We show that all computable torsion Abelian groups have LOGSPACE presentations and we show that the groups ${\mathbb {Z}, Z(p^{\infty})}$ , and the additive group of the rationals have LOGSPACE presentations over a standard universe such as the tally representation and the binary representation of the natural numbers. We also study the effective categoricity of such groups. For (...) example, we give conditions are given under which two isomorphic LOGSPACE structures will have a linear space isomorphism. (shrink)

In this paper, we study the lower semilattice of NP-subspaces of both the standard polynomial time representation and the tally polynomial time representation of a countably infinite dimensional vector space V∞ over a finite field F. We show that for both the standard and tally representation of V∞, there exists polynomial time subspaces U and W such that U + V is not recursive. We also study the NP analogues of simple and maximal subspaces. We show that the existence of (...) P-simple and NP-maximal subspaces is oracle dependent in both the tally and standard representations of V∞. This contrasts with the case of sets, where the existence of NP-simple sets is oracle dependent but NP-maximal sets do not exist. We also extend many results of Nerode and Remmel concerning the relationship of P bases and NP-subspaces in the tally representation of V∞ to the standard representation of V∞. (shrink)

This paper is a continuation of the authors' work , where the main problem considered was whether a given recursive structure is recursively isomorphic to a polynomial-time structure. In that paper, a recursive Abelian group was constructed which is not recursively isomorphic to any polynomial-time Abelian group. We now show that if every element of a recursive Abelian group has finite order, then the group is recursively isomorphic to a polynomial-time group. Furthermore, if the orders are bounded, then the group (...) is recursively isomorphic to a polynomial-time group with universe A being the set of tally representations of natural numbers Tal = s{;1s};* or the set of binary representations of the natural numbers Bin. We also construct a recursive Abelian group with all elements of finite order but which has elements of arbitrary large finite order which is not isomorphic to any polynomial-time group with universe Tal or Bin. Similar results are obtained for structures , where f is a permutation on the set A. (shrink)

A computable graph is constructed which is not computably isomorphic to any polynomial-time graph with a standard universe . Conditions are given under which a computable graph is computably isomorphic to a polynomial-time graph with a standard universe — for example, if every vertex has finite degree. Two special types of graphs are studied. It is shown that any computable tree is recursively isomorphic to a p-time tree with standard universe and that any computable equivalence relation is computably isomorphic to (...) a p-time equivalence relation with standard universe. (shrink)