P not= NP for infinite time Turing machines

2001/06/11 by Ralf Schindler, Schindler, Ralf
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Cellular Automata and Applications #Computability, Logic, AI Algorithms #DNA and Biological Computing #math.LO #msc:03E15 #msc:68Q15

paper · pdf · doi:10.48550/arxiv.math/0106087

2 pages

arxiv created 2001/06/11 · arxiv updated 2009/11/30

Abstract

We state a version of the P=?NP problem for infinite time Turing machines. It is observed that P not= NP for this version.

Related

• Separation of P and NP
• On the questions P ?= NP ∩ co-NP and NP ?= co-NP for infinite time Turing machines
• P = NP
• Philosophical Solution to P=?NP: P is Equal to NP
• Postulate-based proof of the P != NP hypothesis