On total functions, existence theorems and computational complexity

DOI10.1016/0304-3975(91)90200-LzbMATH Open0731.68036MaRDI QIDQ808245FDOQ808245

Authors: Nimrod Megiddo, Christos Papadimitriou

Publication date: 1991

Published in: Theoretical Computer Science (Search for Journal in Brave)

Recommendations

Towards a unified complexity theory of total functions
On the complexity of the parity argument and other inefficient proofs of existence
Computational complexity of fixed points and intersection points
Towards a Unified Complexity Theory of Total Functions
On the Complexity of Nash Equilibria and Other Fixed Points

Nondeterministic multivalued functions total functions from NP

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)

Cites Work

Title not available (Why is that?)
Complementary pivot theory of mathematical programming
Title not available (Why is that?)
Bimatrix Equilibrium Points and Mathematical Programming
How easy is local search?
A Partition Theorem for Euclidean n-Space
Relative complexity of checking and evaluating
Nash and correlated equilibria: Some complexity considerations
Homotopy Continuation Methods for Nonlinear Complementarity Problems
An interior point potential reduction algorithm for the linear complementarity problem
Every Prime Has a Succinct Certificate
The Complexity of the Lin–Kernighan Heuristic for the Traveling Salesman Problem

Cited In (89)

An oracle separating conjectures about incompleteness in the finite domain
Title not available (Why is that?)
The complexity of gradient descent: CLS = PPAD $\cap$ pls
Title not available (Why is that?)
Constant rank two-player games are PPAD-hard
Fixed-Parameter Algorithms for the Kneser and Schrijver Problems
PPAD-complete pure approximate Nash equilibria in Lipschitz games
On the upper bounds for complexities of discrete functions
The classes PPA-$k$: existence from arguments modulo $k$
Consensus-Halving: Does It Ever Get Easier?
The journey from NP to TFNP hardness
Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
The parameterized complexity of welfare guarantees in Schelling segregation
Typical forcings, NP search problems and an extension of a theorem of Riis
PPAD is as hard as LWE and iterated squaring
Relativization of Gurevich’s Conjectures
PPAD-complete approximate pure Nash equilibria in Lipschitz games
Computational tameness of classical non-causal models
On the Computational Complexity of Positive Linear Functionals on $$\mathcal{C}[0;1]$$
Note on constrained long choice with multiple beginning elements
Title not available (Why is that?)
Further collapses in $\mathsf{TFNP}$
The frontier of intractability for EFX with two agents
The classes PPA-$k$: existence from arguments modulo $k$
Equilibria for games with combined qualitative and quantitative objectives
Incremental delay enumeration: space and time
Hardness of continuous local search: query complexity and cryptographic lower bounds
Characterising the intersection of QMA and coQMA
On the Complexity of Equilibrium Computation in First-Price Auctions
The Hairy Ball Problem is PPAD-Complete.
Towards a unified complexity theory of total functions
Nested PLS
Efficient approximation algorithms for the subset-sums equality problem.
The structure and complexity of Nash equilibria for a selfish routing game
On the complexity of finding a Caristi's fixed point
Reductions in \textbf{PPP}
The fibre of P-matrices: the recursive construction of all matrices with positive principal minors
Quantum and classical query complexities of local search are polynomially related
On the black-box complexity of Sperner's Lemma
On the complexity of stable fractional hypergraph matching
Mortality of Iterated Piecewise Affine Functions over the Integers: Decidability and Complexity (extended abstract)
Total functions in QMA
Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation
Nash equilibria: complexity, symmetries, and approximation
Time hierarchies for cryptographic function inversion with advice
Discrete versions of the KKM lemma and their PPAD-completeness
The Veblen functions for computability theorists
A Sperner lemma complete for PPA
Approximate counting and NP search problems
The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich
A finite set of functions with an EXPTIME-complete composition problem
Propositional proofs and reductions between NP search problems
An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups
A Mihalisin-Klee theorem for fans
Hardness results for consensus-halving
Unique End of Potential Line
On the complexity of the parity argument and other inefficient proofs of existence
Does the polynomial hierarchy collapse if onto functions are invertible?
The complexity of the parity argument with potential
Recent development in computational complexity characterization of Nash equilibrium
Continuous verifiable delay functions
Unique end of potential line
Eisenberg-Gale markets: algorithms and game-theoretic properties
Good hidden $P$-matrix sandwiches
Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium
Simple search methods for finding a Nash equilibrium
Satisfactory graph partition, variants, and generalizations
The computational content of Walras' existence theorem
On the complexity of collision resistant hash functions: new and old black-box separations
Towards a Unified Complexity Theory of Total Functions
Mean-payoff games with $\omega$-regular specifications
Structure versus hardness through the obfuscation lens
TFNP: an update
Computational aspects of the colorful Carathéodory theorem
Combinatorial nullstellensatz modulo prime powers and the parity argument
The Complexity of Public-Key Cryptography
A CSP-Based Approach for Solving Parity Game
Simple complexity from imitation games
Adventures in monotone complexity and TFNP
Did the train reach its destination: the complexity of finding a witness
Computable total functions on metric algebras, universal algebraic specifications and dynamical systems
Computing equilibria: a computational complexity perspective
On functional complexity and superpositions of functions
The complexity of finding fair independent sets in cycles
On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
Type 2 computational complexity of functions on Cantor's space
The Hairy Ball problem is PPAD-complete
Two's company, three's a crowd: consensus-halving for a constant number of agents
The complexity of computational problems about Nash equilibria in symmetric win-lose games

This page was built for publication: On total functions, existence theorems and computational complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q808245)