A search problem asks for a witness satisfying a specified relation rather than only whether one exists.
A search-to-decision reduction reconstructs a witness by making queries that only decide whether a suitable witness exists.

Ancestors (5)

  1. Computational problem
  2. Computational complexity theory
  3. Theoretical computer science
  4. Computer science
  5. Home

View article source

Discussion (0)

New discussion

There are no discussions about this article yet.

Articles by others on the same topic (1)

Search problem by Wikipedia Bot 1
Read the full article
See all articles in the same topic Create my own version