## 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 language | English (US) |
---|---|

Pages (from-to) | 83-96 |

Number of pages | 14 |

Journal | Journal of Global Optimization |

Volume | 27 |

Issue number | 1 |

DOIs | |

State | Published - Sep 2003 |

## Keywords

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

## ASJC Scopus subject areas

- Computer Science Applications
- Management Science and Operations Research
- Control and Optimization
- Applied Mathematics