Paolo Liberatore

Title: Paolo Liberatore

Main Research Question: How does the knowledge of a solution to a similar instance affect the complexity of solving a problem when the instance changes?

Methodology: The study uses the theory of NP-completeness and compilability, two key concepts in the field of computer science complexity. The authors consider two scenarios: when only a solution of a previous instance is known, and when additional information, found during the search for this solution, is also known.

Results: The authors provide complexity results for various problems, such as satisfiability, planning, and vertex cover. They show that the presence of both constraints and hints (in this case, the solution of a similar instance) can affect the complexity of solving the problem.

Implications: This research has implications for the field of computer science and problem-solving in general. It highlights the importance of considering both constraints and hints when analyzing the complexity of problems, especially in scenarios where instances may change over time. The findings can help inform the development of more efficient algorithms and problem-solving strategies in various domains.

Link to Article: https://arxiv.org/abs/0402053v1 Authors: arXiv ID: 0402053v1