Loading...
Please wait, while we are loading the content...
Similar Documents
P ̸ = np for infinite time turing machines (2001).
| Content Provider | CiteSeerX |
|---|---|
| Author | Ralf Schindler, A. |
| Abstract | Abstract. We state a version of the “P =?NP ” problem for infinite time Turing machines. It is observed that P ̸ = NP for this version. Infinite time Turing machines were introduced in [1]. The purpose of this note is to point out that P ̸ = NP for a transfinite version of the “P =?NP” problem. A “real ” is considered an element of 2 ω, i.e., an infinite sequence of 0’s and 1’s. We’ll write R for 2 ω. It will be convenient to think of a Turing machine to come with two halting states, the accept state, and the reject state. Definition 0.1 Let A ⊂ R. We say that A is decidable in polynomial time, or A ∈ P, if there are a Turing machine T and some m < ω such that (a) T decides A (i.e, x ∈ A iff T accepts x), and (b) T halts on all inputs after < ω m many steps. With infinite time Turing machines, all inputs (i.e., reals) should be counted as having the same length, namely ω. So it appears reasonable to have a polynomial time Turing machine to be one which always halts after < ω m many steps, for some fixed m < ω. Definition 0.2 Let A ⊂ R, and let α ≤ ω1 + 1. We say that A is in Pα if there are a Turing machine T and some β < α such that (a) T decides A (i.e, x ∈ A iff T accepts x), and (b) T halts on all inputs after < β many steps. Of course, P = Pω ω. Moreover, Pω1+1 is just the class of all A ⊂ R which are decided by some Turing machine. Also: |
| File Format | |
| Publisher Date | 2001-01-01 |
| Access Restriction | Open |
| Subject Keyword | Infinite Time Turing Machine Turing Machine Many Step Iff Accepts Infinite Time Np Problem Polynomial Time Transfinite Version Infinite Sequence Reject State Accept State |
| Content Type | Text |
| Resource Type | Article |
