Strong and robustly strong polynomial-time reducibilities to sparse sets (Q1177170)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Strong and robustly strong polynomial-time reducibilities to sparse sets |
scientific article; zbMATH DE number 20022
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Strong and robustly strong polynomial-time reducibilities to sparse sets |
scientific article; zbMATH DE number 20022 |
Statements
Strong and robustly strong polynomial-time reducibilities to sparse sets (English)
0 references
26 June 1992
0 references
Strong nondeterministic machines are those types of Turing machines that define the class \(\text{NP}\cap\text{co-NP}\). When equipped with the additional feature of an ''advice'', as studied by Karp and Lipton, two different definitions are possible: a robust and non-robust version. Both versions are studied in this paper and compared. Related to this research, an oracle-restricted positive relativization of the probabilistic class ZPP is developed.
0 references
nondeterminism
0 references
robust reducibility
0 references
