Studying the complexity of global verification for NP-hard discrete optimization problems

Derek E. Armstrong, Sheldon H. Jacobson

Research output: Contribution to journalArticlepeer-review

Abstract

This paper examines the complexity of global verification for MAX-SAT, MAX-k-SAT (for k≥3), Vertex Cover, and Traveling Salesman Problem. These results are obtained by adaptations of the transformations that prove such problems to be NP-complete. The class of problems PGS is defined to be those discrete optimization problems for which there exists a polynomial time algorithm such that given any solution ω, either a solution can be found with a better objective function value or it can be concluded that no such solution exists and ω is a global optimum. This paper demonstrates that if any one of MAX-SAT, MAX-k-SAT (for k≥3), Vertex Cover, or Traveling Salesman Problem are in PGS, then P=NP.

Original languageEnglish (US)
Pages (from-to)83-96
Number of pages14
JournalJournal of Global Optimization
Volume27
Issue number1
DOIs
StatePublished - Sep 2003

Keywords

  • Computational complexity
  • Discrete optimization problems
  • Local search algorithms
  • NP-hard

ASJC Scopus subject areas

  • Control and Optimization
  • Applied Mathematics
  • Business, Management and Accounting (miscellaneous)
  • Computer Science Applications
  • Management Science and Operations Research

Fingerprint

Dive into the research topics of 'Studying the complexity of global verification for NP-hard discrete optimization problems'. Together they form a unique fingerprint.

Cite this