AN NP-COMPLETE LANGUAGE ACCEPTED IN LINEAR TIME BY A ONE-TAPE TURING MACHINE

被引：12

作者：

MICHEL, P

机构：

[1] Université Paris 7, 75005 Paris

来源：

THEORETICAL COMPUTER SCIENCE | 1991年 / 85卷 / 01期

关键词：

D O I：

10.1016/0304-3975(91)90054-6

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We consider one-tape nondeterministic Turing machines, i.e. with a unique worktape on which the input is written. It is known that there are nonregular languages accepted by such machines in time O(n log log n), and an NP-complete language accepted in time O(n log n). We exhibit nonregular languages accepted by such machines in time n + O(square-root n log n) or n + O(log2 n), and an NP-complete language accepted in time n + O(square-root n log n), by using a tight padding method.

引用

页码：205 / 212

页数：8

共 10 条

[1]

ALT H, 1976, AUTOMATA LANGUAGES P, P339

[2]

Fagin R., 1974, COMPLEXITY COMPUTATI, V7, P43

[3]

Harrison M, 1978, INTRO FORMAL LANGUAG

[4] COMPUTATIONAL COMPLEXITY OF ONE-TAPE TURING MACHINE COMPUTATIONS [J].