On search decision and the efficiency of polynomial-time algorithms

1989/01/01 by Michael R. Fellows, Michael A. Langston · 3 citations
Computer Science · Mathematics · #semigroups and automata theory #Computability, Logic, AI Algorithms #Advanced Combinatorial Mathematics #Computer science #Algorithm #Mathematical optimization #Mathematics

paper · pdf · doi:10.1145/73007.73055

openalex publication_date 1989/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31

Abstract

Recent advances in well-partial-order theory, especially the seminal contributions of Robertson and Seymour, have troubling consequences for those who would equate tractability with polynomial-time decidability. Specifically:

Citations

• Nonconstructive tools for proving polynomial-time decidability
• Graph minors. I. Excluding a forest
• Graph minors. V. Excluding a planar graph
• Constructive results from graph minors: linkless embeddings
• Theorie der Normalflächen: Ein Isotopiekriterium für den Kreisknoten
• The NP-completeness column: An ongoing guide

Cited by

• Obstruction set isolation for the gate matrix layout problem
• Minimal acyclic forbidden minors for the family of graphs with bounded path-width
• Pathwidth [wikipedia]