Towards a Unified Complexity Theory of Total Functions
From MaRDI portal
Recommendations
- Towards a unified complexity theory of total functions
- On total functions, existence theorems and computational complexity
- scientific article; zbMATH DE number 3941436
- UNIFORM CHARACTERIZATIONS OF COMPLEXITY CLASSES OF FUNCTIONS
- Complexity of functions: Some questions, conjectures, and results
- On the structure of the space of complexity partial functions
- Complexity theory for spaces of integrable functions
- Computability theory of generalized functions
- scientific article; zbMATH DE number 1136092
- The bounded complexity function versus the unbounded complexity function
Cites work
- A method for obtaining digital signatures and public-key cryptosystems
- Approximate counting by hashing in bounded arithmetic
- Complexity classes without machines: on complete languages for UP
- scientific article; zbMATH DE number 3814972 (Why is no real title available?)
- scientific article; zbMATH DE number 4059391 (Why is no real title available?)
- scientific article; zbMATH DE number 512985 (Why is no real title available?)
- scientific article; zbMATH DE number 819737 (Why is no real title available?)
- Implicit proofs
- Integer factoring and modular square roots
- On the complexity of finding falsifying assignments for Herbrand disjunctions
- On the complexity of polyhedral separability
- On the complexity of the parity argument and other inefficient proofs of existence
- Polynomial size proofs of the propositional pigeonhole principle
- Propositional proofs and reductions between NP search problems
- Quasipolynomial size proofs of the propositional pigeonhole principle
- Settling the complexity of computing two-player Nash equilibria
- Some consequences of cryptographical conjectures for \(S_2^1\) and EF
- The complexity of computing a Nash equilibrium
- The NP search problems of Frege and extended Frege proofs
- The relative complexity of NP search problems
- The relative efficiency of propositional proof systems
Cited in
(8)- On functional complexity and superpositions of functions
- Towards a unified complexity theory of total functions
- Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation
- The complexity space of partial functions: a connection between complexity analysis and denotational semantics
- The NP search problems of Frege and extended Frege proofs
- FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
- Total functions in the polynomial hierarchy
- On total functions, existence theorems and computational complexity
This page was built for publication: Towards a Unified Complexity Theory of Total Functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4993302)
