2 citations · 2 across the 2 of their papers we have counts for
Showing math.LOShow all
2 papers · 1 filter
math.LO2003★ 2 cited
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…
math.LO2003
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…