Extending Downward Collapse from 1-versus-2 Queries to<i>m</i>-versus-<i>m</i>+ 1 Queries (Q5317200)
From MaRDI portal
scientific article; zbMATH DE number 2205896
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Extending Downward Collapse from 1-versus-2 Queries to<i>m</i>-versus-<i>m</i>+ 1 Queries |
scientific article; zbMATH DE number 2205896 |
Statements
Extending Downward Collapse from 1-versus-2 Queries to<i>m</i>-versus-<i>m</i>+ 1 Queries (English)
0 references
16 September 2005
0 references
computational complexity theory
0 references
no-search easy-hard technique
0 references
downward collapse
0 references
upward separation
0 references
downward translation of equality
0 references
Boolean hierarchy
0 references
polynomial hierarchy
0 references
