EUVIMEDEUVIMED entdecken
Crossref

ON OPTIMAL INVERTERS

YIJIA CHEN, JÖRG FLUM

The Bulletin of Symbolic Logic · 2014

DOI: 10.1017/bsl.2013.2 ↗

Kurz gefasst

Fachartikel in der Zeitschrift The Bulletin of Symbolic Logic, 2014. Verfasst von YIJIA CHEN und 1 weiteren Autor:innen. Die Arbeit wurde bisher 4-mal zitiert (Crossref) und nennt 27 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Leonid Levin showed that every algorithm computing a function has an optimal inverter. Recently, we applied his result in various contexts: existence of optimal acceptors, existence of hard sequences for algorithms and proof systems, proofs of Gödel’s incompleteness theorems, analysis of the complexity of the clique problem assuming the nonuniform Exponential Time Hypothesis. We present all these applications here. Even though a simple diagonalization yields Levin’s result, we believe that it is worthwhile to be aware of the explicit result. The purpose of this survey is to convince the reader of our view.

Zitieren

APA

CHEN, Y., & FLUM, J. (2014). ON OPTIMAL INVERTERS. The Bulletin of Symbolic Logic. https://doi.org/10.1017/bsl.2013.2

Vancouver

CHEN Y, FLUM J. ON OPTIMAL INVERTERS. The Bulletin of Symbolic Logic. 2014. doi:10.1017/bsl.2013.2

BibTeX
@article{CHEN2014,
  author = {CHEN, YIJIA and FLUM, JÖRG},
  title = {ON OPTIMAL INVERTERS},
  journal = {The Bulletin of Symbolic Logic},
  year = {2014},
  doi = {10.1017/bsl.2013.2}
}
Kostenlos starten →