Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-23T11:48:23.915Z Has data issue: false hasContentIssue false
  • English
  • Français

ON OPTIMAL INVERTERS

Published online by Cambridge University Press:  13 May 2014

YIJIA CHEN  and
JÖRG FLUM
YIJIA CHEN
Affiliation:
DEPARTMENT OF COMPUTER SCIENCE, SHANGHAI JIAOTONG UNIVERSITY, XUHUI, SHANGHAI, CHINAE-mail:[email protected]
JÖRG FLUM
Affiliation:
MATHEMATISCHES INSTITUT, ALBERT-LUDWIGS-UNIVERSITÄT FREIBURG, FREIBURG IM BREISGAU, BADEN-WÜRTTEMBERG, GERMANYE-mail:[email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

Type
Articles
Information
Bulletin of Symbolic Logic , Volume 20 , Issue 1 , March 2014 , pp. 1 - 23
Copyright
Copyright © The Association for Symbolic Logic 2014 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Chen, Y., Eickmeyer, K., and Flum, J., The exponential time hypothesis and the parameterized clique problem, Proceedings of the 7th International Symposium on Parameterized and Exact Computation (IPEC’12), Lecture Notes in Computer Science, Springer, 2012, pp. 13–24.Google Scholar
Chen, Y. and Flum, J., On p-optimal proof systems and logics for PTIME, Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP’10, Track B), Lecture Notes in Computer Science, vol. 6199, Springer, 2010, pp. 321–332.Google Scholar
Chen, Y. and Flum, J., Listings and logics, Proceedings of the 26th Annual IEEE Symposium on Logic in Computer Science (LICS’11), IEEE Computer Society, 2011, pp. 165–174.Google Scholar
Chen, Y. and Flum, J., From almost optimal algorithms to logics for complexity classes via listings and a halting problem. Journal of the ACM, vol. 59 (2012), no. 4, article 17.Google Scholar
Chen, Y., Flum, J., and Müller, M., Consistency and optimality, Proceedings of the 7th Computability in Europe, Mathematical Theory and Computational Practice (CiE’11), Lecture Notes in Computer Science, vol. 6735, 2011, pp. 61–70.Google Scholar
Chen, Y., Flum, J., and Müller, M., Hard instances of algorithms and proof systems, Proceedings of How the World Computes - Turing Centenary Conference and the 8th Computability in Europe, Mathematical Theory and Computational Practice (CiE’12), Lecture Notes in Computer Science, vol. 7318, 2012, pp. 118–128.Google Scholar
Christennsen, N., Levin’s optimal search theorem and Blum’s speedup theorem. Master Thesis, University of Copenhagen, 1999.Google Scholar
Downey, R. and Fellows, M., Fixed-parameter tractability and completeness III: Some structural aspects of the W-hierarchy, Complexity Theory (Ambos-Spies, K., Homer, S., and Schöning, U., editors), Cambridge University Press, Cambridge, UK, 1993, pp. 166–191.Google Scholar
Gödel, K., Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I. Monatshefte für Mathematik und Physik, vol. 38 (1931), pp. 173–198.Google Scholar
Gurevich, Y., On Kolmogorov machines and related issues. Bulletin of the European Association for Theoretical Computer Science, vol. 35 (1988), pp. 71–81.Google Scholar
Hitchcock, J. M. and Pavan, A., Hardness hypotheses, derandomization, and circuit complexity, Proceedings of the 24th International Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS’04), 2004, pp. 336–347.Google Scholar
Hutter, M., The fastest and shortest algorithm for all well-defined problems. International Journal of Foundations of Computer Science, vol. 13 (2002), no. 3, pp. 431–443.Google Scholar
Impagliazzo, R., Paturi, R., and Zane, F., Which problems have strongly exponential complexity? Journal of Computer and System Sciences, vol. 63 (2001), pp. 512–530.Google Scholar
Köbler, J. and Messner, J., Complete problems for promise classes by optimal proof systems for test sets, Proceedings of the 13th Annual IEEE Conference on Computational Complexity (CCC’98), Springer, 1998, pp. 132–140.Google Scholar
Krajíc̆ek, J., Bounded arithmetic, propositional logic, and complexit theory, Cambridge University Press, 1995.Google Scholar
Krajíc̆ek, J. and Pudlák, P., Propositional proof systems, the consistency of first order theories and the complexity of computations. The Journal of Symbolic Logic, vol. 54 (1989), no. 3, pp. 1063–1079.Google Scholar
Levin, L., Universal sequential search problems. Problems of Information Transmission, vol. 9 (1973), no. 3, pp. 265–266.Google Scholar
Mayordomo, E., Almost every set in exponential time is P-bi-immune. Theoretical Computer Science, vol. 136 (1994), no. 2, pp. 487–506.Google Scholar
Messner, J., On optimal algorithms and optimal proof systems, Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science, (STACS’99), Lecture Notes in Computer Science, Springer, 1999, pp. 541–550.Google Scholar
Messner, J., On the simulation order of proof systems. Ph.D. thesis, University of Erlangen, 2000.Google Scholar
Papadimitriou, C. H., Computational complexity, Addison-Wesley, New York, 1994.Google Scholar
Sadowski, Z., On an optimal deterministic algorithm for SAT, Proceedings of Computer Science Logic 1998 (CSL ’98), Lecture Notes in Computer Science, vol. 1584, Springer, 1998, pp. 179–187.Google Scholar
Sadowski, Z., On an optimal propositional proof system and the structure of easy subsets. Theoretical Computer Science, vol. 288 (2002), no. 1, pp. 181–193.Google Scholar
Sadowski, Z., Optimal proof systems, optimal acceptors and recursive presentability. Fundamenta Informaticae, vol. 79 (2007), no. 1–2, pp. 169–185.Google Scholar
Stockmeyer, L., The complexity of decision problems in automata theory, Ph.D. thesis, MIT, 1974.Google Scholar
Turing, A.M., On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, vol. 2 (1936), pp. 230–265.Google Scholar
Verbitsky, O. V., Optimal algorithms for coNP-sets and the problem EXP=NEXP. Matematicheskie zametki, vol. 50 (1979), no. 2, pp. 37–46.Google Scholar