NP-completeness: A retrospective

DOI10.1007/3-540-63165-8_160zbMath1401.68100OpenAlexW1500050811MaRDI QIDQ4571936

Christos H. Papadimitriou

Publication date: 4 July 2018

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-63165-8_160

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (16)

Generating all maximal models of a Boolean expression ⋮ On the fixed-parameter tractability of the equivalence test of monotone normal forms ⋮ Enumerating minimal dominating sets in chordal bipartite graphs ⋮ A global parallel algorithm for enumerating minimal transversals of geometric hypergraphs ⋮ An incremental polynomial time algorithm to enumerate all minimal edge dominating sets ⋮ Computational aspects of monotone dualization: a brief survey ⋮ On the complexity of monotone dualization and generating minimal hypergraph transversals ⋮ How to Apply SAT-Solving for the Equivalence Test of Monotone Normal Forms ⋮ Polynomial-time dualization of \(r\)-exact hypergraphs with applications in geometry ⋮ Computational aspects of mining maximal frequent patterns ⋮ On the fractional chromatic number of monotone self-dual Boolean functions ⋮ Algorithms for compact letter displays: comparison and evaluation ⋮ Lower bounds for three algorithms for transversal hypergraph generation ⋮ Quasi-polynomial algorithms for list-coloring of nearly intersecting hypergraphs ⋮ Efficient Reasoning for Inconsistent Horn Formulae ⋮ Monotone Boolean dualization is in co-NP\([\log^{2}n\).]

Cites Work

• Unnamed Item
• Unnamed Item
• On generating all maximal independent sets
• How easy is local search?
• Testing the universal instance assumption
• Optimization, approximation, and complexity classes
• On the complexity of the parity argument and other inefficient proofs of existence
• On limited nondeterminism and the complexity of the V-C dimension
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• New directions in cryptography
• On the Structure of Polynomial Time Reducibility
• P-Complete Approximation Problems
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• Reducibility among Combinatorial Problems
• The complexity of satisfiability problems
• Node-and edge-deletion NP-complete problems
• The complexity of theorem-proving procedures

This page was built for publication: NP-completeness: A retrospective