No label defined (Q3976040)
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 18636
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 18636 |
Statements
26 June 1992
0 references
nonuniform computation models
0 references
random access machines
0 references
separation
0 references
0.8245025873184204
0 references
0.7271231412887573
0 references
0.7219077348709106
0 references
[For the entire collection see Zbl 0731.00026.] A series of polynomially time-bounded complexity classes (uniform and nonuniform, sequential and parallel, deterministic as well as nondeterministic) based on random access machines aided with the arithmetic operation set \(S\subseteq\{+,-,*,\text{DIV,DIV}_ c,\text{MOD},\dots\}\) (so-called \(S\)-RAM machines) is defined. The authors prove that the \(\{+,-,\text{DIV}_ c\}\)-polynomial class differs from the \(\{+,-,\text{DIV}_ c\}-N\) one. A number of other separation results concerning the above mentioned complexity classes are obtained, mostly for the operation set \(S=\{+,- ,*\}\).
0 references
