COMBINATORICS, COMPLEXITY, AND RANDOMNESS

Chia sẻ: Ledung Ledung | Ngày: | Loại File: PDF | Số trang:0

0
69
lượt xem
4
download

COMBINATORICS, COMPLEXITY, AND RANDOMNESS

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Upon reading Cook’s paper, I realized at once that his concept of an archetypal combinatorial problem was a formalization of an idea that had long been part of the folklore of combinatorial optimization. Workers in that field knew that the integer programming problem, which is essentially the problem of deciding whether a system of linear inequalities has a solution in integers, was general enough to express the constraints of any of the commonly encountered combinatorial optimization problems. Dantzig had published a paper on that theme in 1960. Because Cook was interested in theorem proving rather than combinatorial optimization, he had chosen a different archetypal problem, but the basic idea was the same. However,......

Chủ đề:
Lưu

Nội dung Text: COMBINATORICS, COMPLEXITY, AND RANDOMNESS

Đồng bộ tài khoản