scientific article; zbMATH DE number 18636
[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=\{+,- ,*\}\).
- On solving hard problems by polynomial-size circuits
- On the complexity of the computation of certain classes of polynomials of several variables
- scientific article; zbMATH DE number 4134023 (Why is no real title available?)
- scientific article; zbMATH DE number 3932433 (Why is no real title available?)
- scientific article; zbMATH DE number 1760347 (Why is no real title available?)
- scientific article; zbMATH DE number 827987 (Why is no real title available?)
- On genuinely time bounded computations
- scientific article; zbMATH DE number 6796098 (Why is no real title available?)
- The black-box query complexity of polynomial summation
- On the cell probe complexity of polynomial evaluation
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3976040)
