The Complexity of Complexity (Q2973719)

From MaRDI portal

Jump to:navigation, search

scientific article

Language	Label	Description	Also known as
English	The Complexity of Complexity	scientific article

Statements

scholarly article

0 references

The Complexity of Complexity (English)

0 references

Computability and Complexity

0 references

publication date

4 April 2017

0 references

Eric W. Allender

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1007/978-3-319-50062-1_6

0 references

Reducing the complexity of reductions

0 references

NL-printable sets and nondeterministic Kolmogorov complexity

0 references

Curiouser and Curiouser: The Link between Incompressibility and Complexity

0 references

Investigations Concerning the Structure of Complete Sets

0 references

Reductions to the set of random strings: The resource-bounded case

0 references

What can be efficiently reduced to the Kolmogorov-random strings?

0 references

Power from Random Strings

0 references

Zero Knowledge and Circuit Minimization

0 references

0 references

Limits on the computational power of random strings

0 references

Minimum Circuit Size, Graph Isomorphism, and Related Problems

0 references

The Minimum Oracle Circuit Size Problem.

0 references

The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory

0 references

Minimizing Disjunctive Normal Form Formulas and $AC^0$ Circuits Given a Truth Table

0 references

Computational Complexity

0 references

An excursion to the Kolmogorov random strings

0 references

\(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)

0 references

Random strings and tt-degrees of Turing complete C.E. sets

0 references

On the computational power of random strings

0 references

Algorithmic Randomness and Complexity

0 references

Complexity Measures for Public-Key Cryptosystems

0 references

Limitations of Hardness vs. Randomness under Uniform Reductions

0 references

On Characterizations of Randomized Computation Using Plain Kolmogorov Complexity

0 references

0 references

Limitations of Efficient Reducibility to the Kolmogorov Random Strings

0 references

On the NP-Completeness of the Minimum Circuit Size Problem.

0 references

Nondeterministic automatic complexity of overlap-free and almost square-free words

0 references

Circuit minimization problem

0 references

On the complexity of random strings

0 references

Communication Complexity

0 references

On the complexity of communication complexity

0 references

Randomness conservation inequalities; information and independence in mathematical theories

0 references

On the hardness of approximating minimization problems

0 references

Kolmogorov entropy in the context of computability theory

0 references

0 references

0 references

0 references

0 references

Discrete logarithm and minimum circuit size

0 references

A low and a high hierarchy within NP

0 references

0 references

0 references

Identifiers

zbMATH Open document ID

0 references

10.1007/978-3-319-50062-1_6

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

zbMATH DE Number

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:2973719

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Item:Q2973719&oldid=36313627"