Journal of Logic and Computation · 2005 · 28 citations · 2 references
ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsTheory Of ComputationComplexity TheoryComputability TheoryComputational ComplexityComputational Complexity ClassesTime ComplexityTuring MachinesBpp Complexity ClassInfinite Tape Turing MachinesNondeterministic Turing MachinesNp-complete ProblemsPolynomial Time ComplexityTuring Machine CharacterizationsTuring Machine Complexity
Extending results of Schindler, Hamkins and Welch, we establish in the context of infinite time Turing machines that P is properly contained in NP ∩ co-NP. For higher analogues of these classes, we exhibit positive and negative results.
2
Joel David Hamkins, Andy Lewis · Journal of Symbolic Logic · 2000 · 259 citations