Improved lowness results for solvable black-box group problems (Q4370033)

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 1104166
Language Label Description Also known as
default for all languages
No label defined
    English
    Improved lowness results for solvable black-box group problems
    scientific article; zbMATH DE number 1104166

      Statements

      29 November 1998
      0 references
      computational group theory
      0 references
      complexity
      0 references
      decision problems
      0 references
      solvable black-box groups
      0 references
      solvability tests
      0 references
      group isomorphisms
      0 references
      group factorizations
      0 references
      coset intersections
      0 references
      Improved lowness results for solvable black-box group problems (English)
      0 references
      Upper bounds on the complexity of the following decision problems over solvable black-box groups are computed: solvability testing, membership testing, order verification, group isomorphism, group intersection, group factorization, coset intersection, and double-coset membership. It is shown that these problems are either in SPP or in LWPP. (These results are in favor of the belief that these problems are unlikely to be complete for NP). For the entire collection see [Zbl 0879.00061].
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references