Monotonic reductions, representative equivalence and compilation of intractable problems.

Monotonic reductions, representative equivalence and compilation of intractable problems.

The idea of preprocessing part of the input of a problem in order to improve efficiency has been employed by several researchers in several areas of computer science. In this article, we show sufficient conditions to prove that an intractable problem cannot be efficiently solved even allowing an exp...

Mô tả đầy đủ

Chi tiết về thư mục
Xuất bản năm:Journal of the ACM 48, 6 (2001).
Tác giả chính: Liberatore, P.
Định dạng: Bài viết
Ngôn ngữ:English
Những chủ đề:
Theory of computation.
Analysis of algorithms and problem complexity.
Nonnumerical algorithms and problems.
Computing methodologies.
Artificial intelligence.
Problem solving, control methods and search.
Algorithms.
Theory.