Improving the space-bounded version of Muchnik's conditional complexity theorem via ``naive'' derandomization (Q2254499): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
EloiFerrer (talk | contribs) Merged Item from Q3007617 |
||||||||||||||
| (5 intermediate revisions by 4 users not shown) | |||||||||||||||
| aliases / en / 0 | aliases / en / 0 | ||||||||||||||
Improving the Space-Bounded Version of Muchnik’s Conditional Complexity Theorem via “Naive” Derandomization | |||||||||||||||
| description / en | description / en | ||||||||||||||
scientific article | scientific article; zbMATH DE number 5908671 | ||||||||||||||
| Property / title | |||||||||||||||
Improving the Space-Bounded Version of Muchnik’s Conditional Complexity Theorem via “Naive” Derandomization (English) | |||||||||||||||
| Property / title: Improving the Space-Bounded Version of Muchnik’s Conditional Complexity Theorem via “Naive” Derandomization (English) / rank | |||||||||||||||
Normal rank | |||||||||||||||
| Property / zbMATH Open document ID | |||||||||||||||
| Property / zbMATH Open document ID: 1330.68128 / rank | |||||||||||||||
Normal rank | |||||||||||||||
| Property / DOI | |||||||||||||||
| Property / DOI: 10.1007/978-3-642-20712-9_6 / rank | |||||||||||||||
Normal rank | |||||||||||||||
| Property / published in | |||||||||||||||
| Property / published in: Computer Science – Theory and Applications / rank | |||||||||||||||
Normal rank | |||||||||||||||
| Property / publication date | |||||||||||||||
17 June 2011
| |||||||||||||||
| Property / publication date: 17 June 2011 / rank | |||||||||||||||
Normal rank | |||||||||||||||
| Property / zbMATH DE Number | |||||||||||||||
| Property / zbMATH DE Number: 5908671 / rank | |||||||||||||||
Normal rank | |||||||||||||||
| Property / MaRDI profile type | |||||||||||||||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||||||||||||||
Normal rank | |||||||||||||||
| Property / OpenAlex ID | |||||||||||||||
| Property / OpenAlex ID: W1696733972 / rank | |||||||||||||||
Normal rank | |||||||||||||||
| Property / OpenAlex ID | |||||||||||||||
| Property / OpenAlex ID: W2570541819 / rank | |||||||||||||||
Normal rank | |||||||||||||||
| Property / arXiv ID | |||||||||||||||
| Property / arXiv ID: 1009.5108 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Latest revision as of 09:51, 6 May 2024
scientific article; zbMATH DE number 5908671
- Improving the Space-Bounded Version of Muchnik’s Conditional Complexity Theorem via “Naive” Derandomization
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Improving the space-bounded version of Muchnik's conditional complexity theorem via ``naive'' derandomization |
scientific article; zbMATH DE number 5908671 |
|
Statements
Improving the space-bounded version of Muchnik's conditional complexity theorem via ``naive'' derandomization (English)
0 references
Improving the Space-Bounded Version of Muchnik’s Conditional Complexity Theorem via “Naive” Derandomization (English)
0 references
5 February 2015
0 references
17 June 2011
0 references
space-bounded Kolmogorov complexity
0 references
Muchnik's theorem
0 references
Nisan-Wigderson generators
0 references
derandomisation
0 references
extractors
0 references
