No label defined (Q3817599)

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 4090786
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 4090786

      Statements

      0 references
      1988
      0 references
      P-completeness
      0 references
      Mostowski epimorphism
      0 references
      parallel complexity
      0 references
      programming language SETL
      0 references
      replacement construct
      0 references
      [For the entire collection see Zbl 0651.00014.] All concepts of set recursion or SETL-like languages have the realization of the axiom of replacement as a basic construct. Therefore one can state the question, whether parallel complexity classes as NC can be described in notions of the programming language SETL. The author gives a negative answer. The usual replacement construct is too week for a description of NC. An extended replacement construct introduced by the author is too strong, since its parallelization would imply that all P-complete problems would be in NC.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references