The complexity of facets (and some facets of complexity)

From MaRDI portal

Publication:1061485

Jump to:navigation, search

DOI10.1016/0022-0000(84)90068-0zbMath0571.68028OpenAlexW2093454413MaRDI QIDQ1061485

Christos H. Papadimitriou, Mihalis Yannakakis

Publication date: 1984

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

Full work available at URL: https://doi.org/10.1016/0022-0000(84)90068-0

zbMATH Keywords

combinatorial optimization NP coNP complexity class facets of polytopes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Polyhedra and polytopes; regular figures, division of spaces (51M20) Mathematical programming (90C99)

Related Items

Alternating and empty alternating auxiliary stack automata., Knapsack polytopes: a survey, Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete, On the complexity of computing the diameter of a polytope, Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP, NP is as easy as detecting unique solutions, The complexity of combinatorial problems with succinct input representation, Random parallel algorithms for finding exact branchings, perfect matchings, and cycles, Toward the complexity of the existence of wonderfully stable partitions and strictly core stable coalition structures in enemy-oriented hedonic games, Multiple total stable models are definitely needed to solve unique solution problems, Scheduling complete intrees on two uniform processors with communication delays, The unique Horn-satisfiability problem and quadratic Boolean equations., DP-Complete Problems Derived from Extremal NP-Complete Properties, Geometric optimization and the polynomial hierarchy, Polynomial terse sets, Semantic Acyclicity on Graph Databases, Geometric optimization and \(D^ P\)-completeness, The complexity of optimization problems, More complicated questions about maxima and minima, and some closures of NP, The expressive powers of stable models for bound and unbound DATALOG queries, Decompositions of nondeterministic reductions, The landscape of communication complexity classes, The complexity of facets resolved, Probabilistic quantifiers and games, The complexity of recognizing minimally tough graphs, The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^{{\mathcal L}}=A\Pi_ 2^{{\mathcal L}}\), Controlling weighted voting games by deleting or adding players with or without changing the quota, A special case for subset interconnection designs, On computing Boolean connectives of characteristic functions, The complexity of computing minimal unidirectional covering sets, Localising iceberg inconsistencies, Better approximations of non-Hamiltonian graphs, Understanding the complexity of axiom pinpointing in lightweight description logics, On the Complexity of Master Problems, Super-Solutions, Rationality and intelligence, Timed negotiations, Classifying the computational complexity of problems, \(P^{NP[O(\log n)}\) and sparse turing-complete sets for NP], The difference and truth-table hierarchies for NP, Manipulation in communication structures of graph-restricted weighted voting games, On the complexity of test case generation for NP-hard problems, Two tractable subclasses of minimal unsatisfiable formulas, On the complexity of core, kernel, and bargaining set, The computational complexity of evolutionarily stable strategies, The Three-Color and Two-Color TantrixTM Rotation Puzzle Problems Are NP-Complete Via Parsimonious Reductions, The complexity of controlled selection, Why not negation by fixpoint?, Correlation polytopes: Their geometry and complexity, The complexity of reasoning with global constraints, Bounded queries to SAT and the Boolean hierarchy, Negotiation as concurrency primitive, Unique (optimal) solutions: complexity results for identifying and locating-dominating codes, Complexity of DNF minimization and isomorphism testing for monotone formulas, Expressing combinatorial optimization problems by linear programs, Complexity of stability, Acceptance in incomplete argumentation frameworks, On polynomial time one-truth-table reducibility to a sparse set, Integer programs for logic constraint satisfaction, Generalizations of Opt P to the polynomial hierarchy, Removing redundancy from a clause, Polynomial-time compression, On the complexity of propositional knowledge base revision, updates, and counterfactuals, The complexity of lifted inequalities for the knapsack problem, Stack size analysis for interrupt-driven programs, Recognizing frozen variables in constraint satisfaction problems, The complexity of variable minimal formulas, Cognitive hierarchy and voting manipulation in \(k\)-approval voting, Complexity of Data Tree Patterns over XML Documents, The complexity of agent design problems: Determinism and history dependence, How to recycle your facets, Unnamed Item, Combining experts' causal judgments, On the Complexity of Semantic Self-minimization, Weighted graphs defining facets: A connection between stable set and linear ordering polytopes, Exact complexity of exact-four-colorability, Probabilistic polynomial time is closed under parity reductions, Non-clausal redundancy properties, Answers set programs for non-transferable utility games: expressiveness, complexity and applications, Linear connectivity problems in directed hypergraphs, Linear programs for constraint satisfaction problems, Černý's conjecture and the road colouring problem, Complexity results for preference aggregation over (\(m\))CP-nets: Pareto and majority voting, On the computational complexity of determining polyatomic structures by X-rays, Computing only minimal answers in disjunctive deductive databases, The three-color and two-color Tantrix\(^{\text{TM}}\) rotation puzzle problems are NP-complete via parsimonious reductions, On subclasses of minimal unsatisfiable formulas, All superlinear inverse schemes are coNP-hard, Covered clauses are not propagation redundant, On qualitative route descriptions. Representation, agent models, and computational complexity, Complexity and expressive power of deterministic semantics for DATALOG\(^ \neg\)., Commutative queries, On the Complexity of Inverse Mixed Integer Linear Optimization, Bounded queries, approximations, and the Boolean hierarchy, Projection results for vehicle routing, Semantic relevance, Towards the Actual Relationship Between NP and Exponential Time, On the complexity of counting in the polynomial hierarchy, On the computational complexity of qualitative coalitional games, Fast approximations for sums of distances, clustering and the Fermat-Weber problem, Existence of Evolutionarily Stable Strategies Remains Hard to Decide for a Wide Range of Payoff Values, Some rainbow problems in graphs have complexity equivalent to satisfiability problems, Intersection suffices for Boolean hierarchy equivalence, Efficient sensor placement and online scheduling of bin collection, From \texttt{SAT} to \texttt{SAT}-\texttt{UNSAT} using P systems with dissolution rules, Stability, vertex stability, and unfrozenness for special graph classes, On measuring inconsistency in definite and indefinite databases with denial constraints, Unnamed Item, Knowledge-based programs, On the Decomposition of Abstract Dialectical Frameworks and the Complexity of Naive-based Semantics, Complexity of Stability., A large set of non-Hamiltonian graphs, Unnamed Item, Fragments of Bag Relational Algebra: Expressiveness and Certain Answers, THE OPERATORS MIN AND MAX ON THE POLYNOMIAL HIERARCHY, Detecting Inconsistencies in Large Biological Networks with Answer Set Programming

Cites Work

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