Name
Abstract | ||
|---|---|---|
A special case of combinatorial search, the recognition problem is examined in this article. (H,A,f) is a recognition problem if H is a set, A is a set system on H and f:H→{0,1} is a function. Someone chooses an arbitrary x∈H and instead of determining x itself (which is the case in most of the search problems) we only have to determine the value f(x) for the given function f from as few questions of type “is x∈A?” as possible, where A∈A. The smallest number of questions needed in the worst case is called the recognition complexity of f over A on H. After surveying some general results, a new class of set systems is introduced and analyzed, generalizing Yao's model of two-party communication complexity. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1016/S0166-218X(03)00192-6 | Discrete Applied Mathematics |
Keywords | Field | DocType |
94A05,94A50 | Discrete mathematics,Combinatorics,Generalization,Communication complexity,Search problem,Combinatorial search,Partially ordered set,Mathematics,Special case | Journal |
Volume | Issue | ISSN |
137 | 1 | 0166-218X |
Citations | PageRank | References |
0 | 0.34 | 1 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gábor Wiener | 1 | 64 | 10.65 |