Hardness assumptions in the foundations of theoretical computer science

DOI10.1007/s00153-005-0279-xzbMath1095.68037OpenAlexW2035495705MaRDI QIDQ2388429

Jan Krajíček

Publication date: 13 September 2005

Published in: Archive for Mathematical Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00153-005-0279-x

zbMATH Keywords

computational complexityexpository note

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Mathematical problems for the next century
• Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
• Tautologies from Pseudo-Random Generators
• On the weak pigeonhole principle
• Classical physics and the Church--Turing Thesis
• Propositional proof systems, the consistency of first order theories and the complexity of computations
• The relative efficiency of propositional proof systems
• A Pseudorandom Generator from any One-way Function
• Foundations of Cryptography
• Pseudorandom Generators in Propositional Proof Complexity
• Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds
• The complexity of theorem-proving procedures

This page was built for publication: Hardness assumptions in the foundations of theoretical computer science