2 citations · 2 across the 2 of their papers we have counts for
5 papers
P is not equal to NP intersect coNP for Infinite Time Turing Machines
Vinay Deolalikar, Joel David Hamkins, Ralf-Dieter Schindler
Extending results of Schindler [math.LO/0106087] and Hamkins and Welch [math.LO/0212046], we establish in the context of infinite time Turing machines that P is properly contained…
On the questions P ?= NP co-NP and NP ?= co-NP for infinite time Turing machines
Vinay Deolalikar
Schindler recently addressed two versions of the question P NP for Turing machines running in transfinite ordinal time. These versions differ in their definition…
Towers of function fields with extremal properties
Vinay Deolalikar
Certain towers of function fields with complete splitting of rational places at each stage are constructed. Also, families oof towers with positive N/g ratios are described.
Extensions of algebraic function fields with complete splitting of all rational places
Vinay Deolalikar
We introduce the notion of "quasi-symmetric" polynomials, which is a generalization of the notion of symmetry, and is particularly suited to the setting of polynomial rings over fi…
Symmetry, splitting rational places in extensions of function fields and generalization of the Hermitian function field
Vinay Deolalikar
The notion of symmetry in polynomial rings with several indeterminates is generalized to polynomial rings over finite fields. Families of extensions of the projective line over a f…