On lower bounds of the closeness between complexity classes (Q4032931): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
| Property / cites work | |||
| Property / cites work: On Sets Truth-Table Reducible to Sparse Sets / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Complete Problems and Strong Polynomial Reducibilities / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Complete sets and closeness to complexity classes / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Probabilistic complexity classes and lowness / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: PP is as Hard as the Polynomial-Time Hierarchy / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets / rank | |||
Normal rank | |||
Revision as of 15:00, 17 May 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On lower bounds of the closeness between complexity classes |
scientific article |
Statements
On lower bounds of the closeness between complexity classes (English)
0 references
17 May 1993
0 references
structural complexity
0 references
density of the symmetric difference
0 references
closeness of approximation
0 references
lower bound
0 references
