On total functions, existence theorems and computational complexity

DOI10.1016/0304-3975(91)90200-LzbMath0731.68036MaRDI QIDQ808245

Christos H. Papadimitriou, Nimrod Megiddo

Publication date: 1991

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

zbMATH Keywords

Nondeterministic multivalued functions; total functions from NP

Mathematics Subject Classification ID

03D15: Complexity of computation (including implicit computational complexity)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

Quantum and classical query complexities of local search are polynomially related, Propositional proofs and reductions between NP search problems, Nested PLS, The structure and complexity of Nash equilibria for a selfish routing game, On the black-box complexity of Sperner's Lemma, Time hierarchies for cryptographic function inversion with advice, Computing equilibria: a computational complexity perspective, Simple search methods for finding a Nash equilibrium, Satisfactory graph partition, variants, and generalizations, Eisenberg-Gale markets: algorithms and game-theoretic properties, Good hidden \(P\)-matrix sandwiches, A Sperner lemma complete for PPA, Efficient approximation algorithms for the subset-sums equality problem., Simple complexity from imitation games, Does the polynomial hierarchy collapse if onto functions are invertible?, An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups, A CSP-Based Approach for Solving Parity Game

Cites Work

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