{
  "id": "1010.0382",
  "version": "v1",
  "published": "2010-10-03T08:22:03.000Z",
  "updated": "2010-10-03T08:22:03.000Z",
  "title": "Search and witness problems in group theory",
  "authors": [
    "Vladimir Shpilrain"
  ],
  "categories": [
    "math.GR",
    "math.LO"
  ],
  "abstract": "Decision problems are problems of the following nature: given a property P and an object O, find out whether or not the object O has the property P. On the other hand, witness problems are: given a property P and an object O with the property P, find a proof of the fact that O indeed has the property P. On the third hand(?!), search problems are of the following nature: given a property P and an object O with the property P, find something \"material\" establishing the property P; for example, given two conjugate elements of a group, find a conjugator. In this survey our focus is on various search problems in group theory, including the word search problem, the subgroup membership search problem, the conjugacy search problem, and others.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2010-10-03T08:22:03.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "20F10",
      "68Q25"
    ],
    "keywords": [
      "group theory",
      "witness problems",
      "subgroup membership search problem",
      "word search problem",
      "conjugacy search problem"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2010arXiv1010.0382S"
    }
  }
}