Keywords: Turing machine, relativization, NP-completeness, crossing sequence, decidability, lower bound, time complexity, running time, linear timeFull text (file, 881,68 KB)