Lax434930.ExponentialTime
The complexity class EXPTIME
concepts/Lax434930/ExponentialTime.lean · lax-434930
No public endorsements yet.
Loading review…
Sign in with ORCIDConcept map
Definition
A binary language belongs to if a deterministic Turing machine decides membership within transitions on every input of length , for some polynomial . The machine is the finite elementary single-tape machine of lax-554803: input bits are distinct from blank, input appears in its original order, and each transition performs one move or one write. A terminal state's Boolean label gives the answer. The polynomial in the exponent may have any fixed degree; this is the usual EXPTIME, also called EXP.
Lean source view on GitHub
| 1 | import Lax434930.PolynomialTime |
| 2 | import Lax554803.MachineModels |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: The complexity class EXPTIME |
| 7 | type: definition |
| 8 | --- |
| 9 | A binary language belongs to if a deterministic Turing |
| 10 | machine decides membership within transitions on every input |
| 11 | of length , for some polynomial . |
| 12 | The machine is the finite elementary single-tape machine of lax-554803: |
| 13 | input bits are distinct from blank, input appears in its original order, |
| 14 | and each transition performs one move or one write. A terminal state's |
| 15 | Boolean label gives the answer. The polynomial in the exponent may have |
| 16 | any fixed degree; this is the usual EXPTIME, also called EXP. |
| 17 | -/ |
| 18 | |
| 19 | namespace Lax434930.ExponentialTime |
| 20 | |
| 21 | open PolynomialTime Lax554803.MachineModels Turing |
| 22 | |
| 23 | /-- Deterministic time bounded by two to a polynomial in the input length. -/ |
| 24 | def EXPTIME : Set Language := |
| 25 | {A | ∃ (M : SingleTape) (p : Polynomial ℕ), ∀ w : Word, |
| 26 | ∃ c : TM0.Cfg M.Γ M.Q, |
| 27 | Nonempty (StateTransition.EvalsToInTime (TM0.step M.transition) |
| 28 | (TM0.init (w.map M.input)) (some c) (2 ^ p.eval w.length)) ∧ |
| 29 | TM0.step M.transition c = none ∧ (M.accept c.q = true ↔ w ∈ A)} |
| 30 | |
| 31 | end Lax434930.ExponentialTime |
| 32 |
Used by
From Mathlib
none
Community review
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above; your ORCID profile must share a public name.
0 comments