6533b855fe1ef96bd12b1140

RESEARCH PRODUCT

A Logical Characterisation of Linear Time on Nondeterministic Turing Machines

Nicole SchweikardtThomas SchwentickClemens Lautemann

subject

Discrete mathematicsNTIMEComputational complexity theoryUnary operationCombinatoricsNondeterministic algorithmTuring machinesymbols.namesakeNon-deterministic Turing machinesymbolsUnary functionTime complexityComputer Science::Formal Languages and Automata TheoryMathematics

description

The paper gives a logical characterisation of the class NTIME(n) of problems that can be solved on a nondeterministic Turing machine in linear time. It is shown that a set L of strings is in this class if and only if there is a formula of the form ∃f1..∃fk∃R1..∃Rm∀xφv; that is true exactly for all strings in L. In this formula the fi are unary function symbols, the Ri are unary relation symbols and φv; is a quantifierfree formula. Furthermore, the quantification of functions is restricted to non-crossing, decreasing functions and in φv; no equations in which different functions occur are allowed. There are a number of variations of this statement, e.g., it holds also for k = 3. From these results we derive an Ehrenfeucht game characterisation of NTIME(n).

yearjournalcountryeditionlanguage
1999-01-01
https://doi.org/10.1007/3-540-49116-3_13