𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A hierarchy for nondeterministic time complexity

✍ Scribed by Stephen A. Cook

Publisher
Elsevier Science
Year
1973
Tongue
English
Weight
515 KB
Volume
7
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

We prove the following theorem in this paper: For any real numbers rl, r2, 1 ~ rl ~ r2, there is a set .4 of strings which has nondeterministic time complexity n*2, but not nondeterministic time complexity n*l. The computing devices are nondeterministic multitape Turing machines.

πŸ“œ SIMILAR VOLUMES

Complexity and hierarchy: A level rule
Complexity and hierarchy: A level rule
✍ Gad Yagil πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 515 KB

n this article, the connection between structural complexity and hierarchical organization is examined. The following quantitative rule, connecting complexities evaluated at different hierarchical levels, is offered: C A/C is the complexity of an A-level structure evaluated in terms of its C-sublev

A descriptive complexity approach to the
A descriptive complexity approach to the linear hierarchy
✍ Yassine HachaΔ±̈chi πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 204 KB

This paper gives some new logical characterizations of the class of rudimentary languages in the scope of descriptive complexity. These characterizations are based on a logic introduced by Parigot and Pelz to characterize Petri Net languages, and generalized quantiΓΏers of comparison of cardinality.

A Turing machine time hierarchy
A Turing machine time hierarchy
✍ Stanislav Ε½Γ‘k πŸ“‚ Article πŸ“… 1983 πŸ› Elsevier Science 🌐 English βš– 727 KB