On total functions, existence theorems and computational complexity
From MaRDI portal
Publication:808245
DOI10.1016/0304-3975(91)90200-LzbMath0731.68036MaRDI QIDQ808245
Nimrod Megiddo, Christos H. Papadimitriou
Publication date: 1991
Published in: Theoretical Computer Science (Search for Journal in Brave)
Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Equilibria for games with combined qualitative and quantitative objectives, On the Complexity of Equilibrium Computation in First-Price Auctions, TFNP: An Update, Consensus-Halving: Does It Ever Get Easier?, Relativization of Gurevich’s Conjectures, The structure and complexity of Nash equilibria for a selfish routing game, On the black-box complexity of Sperner's Lemma, The Journey from NP to TFNP Hardness, A Mihalisin-Klee theorem for fans, Time hierarchies for cryptographic function inversion with advice, Approximate counting and NP search problems, Computing equilibria: a computational complexity perspective, Constant Rank Two-Player Games are PPAD-hard, Computational tameness of classical non-causal models, Typical forcings, NP search problems and an extension of a theorem of Riis, The complexity of computational problems about Nash equilibria in symmetric win-lose games, On the complexity of collision resistant hash functions: new and old black-box separations, Mean-payoff games with \(\omega\)-regular specifications, PPAD-complete approximate pure Nash equilibria in Lipschitz games, A CSP-Based Approach for Solving Parity Game, Total functions in QMA, Unique end of potential line, Fixed-Parameter Algorithms for the Kneser and Schrijver Problems, PPAD-complete pure approximate Nash equilibria in Lipschitz games, PPAD is as hard as LWE and iterated squaring, An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups, Unnamed Item, Propositional proofs and reductions between NP search problems, Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds, Recent development in computational complexity characterization of Nash equilibrium, Nash equilibria: complexity, symmetries, and approximation, Reductions in \textbf{PPP}, Simple search methods for finding a Nash equilibrium, The Hairy Ball problem is PPAD-complete, Combinatorial nullstellensatz modulo prime powers and the parity argument, The classes PPA-\(k\): existence from arguments modulo \(k\), Structure Versus Hardness Through the Obfuscation Lens, Quantum and classical query complexities of local search are polynomially related, Did the train reach its destination: the complexity of finding a witness, Computational aspects of the colorful Carathéodory theorem, Nested PLS, The classes PPA-\(k\): existence from arguments modulo \(k\), Satisfactory graph partition, variants, and generalizations, Simple complexity from imitation games, Does the polynomial hierarchy collapse if onto functions are invertible?, Incremental delay enumeration: space and time, Unnamed Item, Eisenberg-Gale markets: algorithms and game-theoretic properties, On the complexity of finding a Caristi's fixed point, Good hidden \(P\)-matrix sandwiches, The complexity of the parity argument with potential, An oracle separating conjectures about incompleteness in the finite domain, The fibre of P-matrices: the recursive construction of all matrices with positive principal minors, Continuous verifiable delay functions, Adventures in monotone complexity and TFNP, On the complexity of stable fractional hypergraph matching, Unique End of Potential Line, The Hairy Ball Problem is PPAD-Complete., Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium, The complexity of finding fair independent sets in cycles, Two's company, three's a crowd: consensus-halving for a constant number of agents, Discrete versions of the KKM lemma and their PPAD-completeness, Characterising the intersection of QMA and coQMA, The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich, The Complexity of Public-Key Cryptography, A Sperner lemma complete for PPA, Efficient approximation algorithms for the subset-sums equality problem.
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
