A variant of inductive counting (Q1566745)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1454577
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | A variant of inductive counting |
scientific article; zbMATH DE number 1454577 |
Statements
A variant of inductive counting (English)
0 references
4 June 2000
0 references
We present a new version of the inductive counting, accepting the complement of an NSPACE\((s(n))\) language nondeterministically in space \(O(s(n))\), independent of whether \(s(n)\geqslant\log n\), but using an additional ``one-way pebble'' -- a movable marker placed on the input tape. This reduces the space used by inductive counting to \(\log n+O(s(n))\) bits on the binary work tape and gives the weakest known nondeterministic device accepting a co\(-\)NSPACE\((o(\log n))\) language.
0 references
Computational complexity
0 references
Space complexity
0 references
Sublogarithmic space
0 references
Inductive counting
0 references
0 references
0 references
0.8051685094833374
0 references
0.7872044444084167
0 references
0.771899938583374
0 references
0.7631269097328186
0 references
