Reducibility Among Combinatorial Problems 论文

详细信息

发表日期

2012-01-01

发表年份

2012

摘要

A large class of computational problems involve the determination of properties of graphs, digraphs, integers, arrays of integers, finite families of finite sets, boolean formulas and elements of other countable domains. Through simple encodings from such domains into the set of words over a finite alphabet these problems can be converted into language recognition problems, and we can inquire into their computational complexity. It is reasonable to consider such a problem satisfactorily solved when an algorithm for its solution is found which terminates within a number of steps bounded by a polynomial in the length of the input. Many problems with wide applicability – e.g., set cover, knapsack, hitting set, max cut, and satisfiability – lack a polynomial algorithm for solving them, but also lack a proof that no such polynomial algorithm exists. Hence, they remain “open problems.” This paper references the recent work, “On the Reducibility of Combinatorial Problems ” [1]. BODY A large class of open problems are mutually convertible via poly-time reduc-