On the complexity of the parity argument and other inefficient proofs of existence

From MaRDI portal

Publication:1329155

Jump to:navigation, search

DOI10.1016/S0022-0000(05)80063-7zbMath0806.68048WikidataQ56138406 ScholiaQ56138406MaRDI QIDQ1329155

Christos H. Papadimitriou

Publication date: 13 February 1995

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

zbMATH Keywords

search problems Hamiltonian cubic graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

The NP Search Problems of Frege and Extended Frege Proofs, Inapproximability of Nash Equilibrium, On the Complexity of Equilibrium Computation in First-Price Auctions, TFNP: An Update, When the Players Are Not Expectation Maximizers, A Direct Reduction from k-Player to 2-Player Approximate Nash Equilibrium, Consensus-Halving: Does It Ever Get Easier?, ETR-Completeness for Decision Versions of Multi-player (Symmetric) Nash Equilibria, Settling Some Open Problems on 2-Player Symmetric Nash Equilibria, The Journey from NP to TFNP Hardness, On Solving Systems of Diagonal Polynomial Equations Over Finite Fields, Approximate counting and NP search problems, A Complementary Pivot Algorithm for Market Equilibrium under Separable, Piecewise-Linear Concave Utilities, Constant Rank Two-Player Games are PPAD-hard, A survey of mass partitions, The Computational Complexity of Finding a Mixed Berge Equilibrium for a k-Person Noncooperative Game in Normal Form, Computation of Dynamic Equilibria in Series-Parallel Networks, The complexity of computational problems about Nash equilibria in symmetric win-lose games, NP-completeness: A retrospective, The Exact Computational Complexity of Evolutionarily Stable Strategies, On tightness of the Tsaknakis-Spirakis algorithm for approximate Nash equilibrium, The complexity of searching implicit graphs, SNARGs and PPAD hardness from the decisional Diffie-Hellman assumption, PPAD-complete approximate pure Nash equilibria in Lipschitz games, Public goods games in directed networks, Faster algorithms for \(k\)-\textsc{Subset Sum} and variations, A CSP-Based Approach for Solving Parity Game, On finding constrained independent sets in cycles, Total functions in QMA, Non-interactive universal arguments, Multilinear Games, Fixed-Parameter Algorithms for the Kneser and Schrijver Problems, $$\mathcal {NP}$$-Hardness of Equilibria in Case of Risk-Averse Players, Simultaneous contests with equal sharing allocation of prizes: computational complexity and price of anarchy, PPAD-complete pure approximate Nash equilibria in Lipschitz games, PPAD is as hard as LWE and iterated squaring, Unnamed Item, Unnamed Item, Euler Complexes, Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds, Many-one reductions and the category of multivalued functions, Unnamed Item, Approximating Tverberg points in linear time for any fixed dimension, Towards a Unified Complexity Theory of Total Functions, ARRIVAL: Next Stop in CLS, The classes PPA-\(k\): existence from arguments modulo \(k\), Structure Versus Hardness Through the Obfuscation Lens, Some Tractable Win-Lose Games, The complexity of searching succinctly represented graphs, The Complexity of Computing a Bisimilarity Pseudometric on Probabilistic Automata, The classes PPA-\(k\): existence from arguments modulo \(k\), From Minicrypt to Obfustopia via Private-Key Functional Encryption, CONSISTENCY OF CIRCUIT EVALUATION, EXTENDED RESOLUTION AND TOTAL NP SEARCH PROBLEMS, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, New and simple algorithms for stable flow problems, Unnamed Item, Decomposable obfuscation: a framework for building applications of obfuscation from polynomial hardness, Can PPAD hardness be based on standard cryptographic assumptions?, Minimal and Hyper-Minimal Biautomata, An Algorithmic Proof of the Lovász Local Lemma via Resampling Oracles, Approximate Equilibria for Strategic Two Person Games, Strategic Characterization of the Index of an Equilibrium, Substitution with Satiation: A New Class of Utility Functions and a Complementary Pivot Algorithm, Inapproximability of NP-Complete Variants of Nash Equilibrium, Adventures in monotone complexity and TFNP, On the complexity of stable fractional hypergraph matching, The Hairy Ball Problem is PPAD-Complete., Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem, Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium, Computational complexity of some intelligent computing systems, The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg, Fast Algorithms for Rank-1 Bimatrix Games, Fully Polynomial-Time Approximation Schemes for Fair Rent Division, On Random Symmetric Bimatrix Games, Unnamed Item, The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich, Consensus Halving for Sets of Items, A smooth path-following algorithm for market equilibrium under a class of piecewise-smooth concave utilities, The complexity of equilibria for risk-modeling valuations, Congestion games with malicious players, On the complexity of price equilibria, Computing approximate Nash equilibria in general network revenue management games, On the complexity of constrained Nash equilibria in graphical games, The structure and complexity of Nash equilibria for a selfish routing game, On the black-box complexity of Sperner's Lemma, Computational complexity of computing a quasi-proper equilibrium, On the complexity of an expanded Tarski's fixed point problem under the componentwise ordering, Short proofs of the Kneser-Lovász coloring principle, Games of fixed rank: a hierarchy of bimatrix games, Computing equilibria: a computational complexity perspective, Automatic verification of concurrent stochastic systems, Equilibrium computation in resource allocation games, The give and take game: analysis of a resource sharing game, Pivoting in linear complementarity: Two polynomial-time cases, Computing equilibria for integer programming games, Cutting planes, connectivity, and threshold logic, Equipartition of mass distributions by hyperplanes, On the complexity of stable hypergraph matching, stable multicommodity flow and related problems, Approximation schemes for subset-sums ratio problems, Approximating subset sum ratio via subset sum computations, Typical forcings, NP search problems and an extension of a theorem of Riis, From minicrypt to obfustopia via private-key functional encryption, Complexity of rational and irrational Nash equilibria, \(\mathsf{PPAD}\)-completeness of polyhedral versions of Sperner's lemma, Compactly representing utility functions using weighted goals and the Max aggregator, Integer factoring and modular square roots, A polynomial-time algorithm for the tridiagonal and Hessenberg P-matrix linear complementarity problem, Unique end of potential line, Propositional proofs and reductions between NP search problems, Colorful linear programming, Nash equilibrium, and pivots, Understanding PPA-completeness, Recent development in computational complexity characterization of Nash equilibrium, Equilibria, fixed points, and complexity classes, Nash equilibria: complexity, symmetries, and approximation, A note on proofs of existence of Nash equilibria in finite strategic games, of two players, Long cycles in Hamiltonian graphs, Inverting onto functions., Computing exact solutions of consensus halving and the Borsuk-Ulam theorem, Reductions in \textbf{PPP}, Computing solutions of the multiclass network equilibrium problem with affine cost functions, Semidefinite programming for min-max problems and games, A FPTAS for computing a symmetric leontief competitive economy equilibrium, Good neighbors are hard to find: Computational complexity of network formation, The complexity of uniform Nash equilibria and related regular subgraph problems, The Hairy Ball problem is PPAD-complete, Combinatorial nullstellensatz modulo prime powers and the parity argument, Arc-routing for winter road maintenance, A parity theorem about trees with specified degrees, Exponentiality of the exchange algorithm for finding another room-partitioning, Reversible simulation of space-bounded computations, Solving systems of diagonal polynomial equations over finite fields, Towards a unified complexity theory of total functions, Did the train reach its destination: the complexity of finding a witness, On Stackelberg mixed strategies, On the complexity of deciding bimatrix games similarity, Fixed points, Nash equilibria, and the existential theory of the reals, Smooth calibration, leaky forecasts, finite recall, and Nash dynamics, The complexity of computing a (quasi-)perfect equilibrium for an \(n\)-player extensive form game, The complexity of equilibria: Hardness results for economies via a correspondence with games, Nested PLS, Computing solutions of the paintshop-necklace problem, 2-D Tucker is PPA complete, Solving coloring, minimum clique cover and kernel problems on arc intersection graphs of directed paths on a tree, Well supported approximate equilibria in bimatrix games, The computation of approximate competitive equilibrium is PPAD-hard, Simple complexity from imitation games, Polynomial-size Frege and resolution proofs of \(st\)-connectivity and Hex tautologies, Interdependent defense games with applications to internet security at the level of autonomous systems, The myth of the folk theorem, On the complexity of finding a Caristi's fixed point, Separable and low-rank continuous games, The complexity of the parity argument with potential, No bullying! A playful proof of Brouwer's fixed-point theorem, Cache me if you can: capacitated selfish replication games in networks, Polynomial algorithms for approximating Nash equilibria of bimatrix games, Existence of equilibria in a decentralized two-level supply chain, Continuous verifiable delay functions, The strategic exploitation of limited information and opportunity in networked markets, Deciding probabilistic bisimilarity distance one for probabilistic automata, The relative complexity of NP search problems, A PPA parity theorem about trees in a bipartite graph, Paintshop, odd cycles and necklace splitting, On the complexity of 2D discrete fixed point problem, On the computational complexity of Nash equilibria for \((0,1)\) bimatrix games, Some graphic uses of an even number of odd nodes, The complexity of finding fair independent sets in cycles, Two's company, three's a crowd: consensus-halving for a constant number of agents, Oriented Euler complexes and signed perfect matchings, Discrete versions of the KKM lemma and their PPAD-completeness, The complexity of finding a second Hamiltonian cycle in cubic graphs, Characterising the intersection of QMA and coQMA, Quasipolynomial size proofs of the propositional pigeonhole principle, Fiat-Shamir for repeated squaring with applications to PPAD-hardness and VDFs, Delegation with updatable unambiguous proofs and PPAD-hardness, Faster algorithms for \(k\)-subset sum and variations, A Sperner lemma complete for PPA, Efficient approximation algorithms for the subset-sums equality problem.

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:1329155&oldid=13459123"