Paolo Liberatore: Difference between revisions
Created page with "Title: Paolo Liberatore Main Research Question: How efficient are the popular methods DPLL and resolution for solving the problem of propositional satisfiability, and how hard is it to make the optimal choices during execution? Methodology: The study uses mathematical analysis and computational complexity theory to investigate the efficiency of DPLL and resolution algorithms. It compares the complexity of making optimal choices in these algorithms, such as choosing th..." |
No edit summary |
||
| (One intermediate revision by the same user not shown) | |||
| Line 1: | Line 1: | ||
Title: Paolo Liberatore | Title: Paolo Liberatore | ||
Main Research Question: How | 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 | 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 | 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: | 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/ | Link to Article: https://arxiv.org/abs/0402053v1 | ||
Authors: | Authors: | ||
arXiv ID: | arXiv ID: 0402053v1 | ||
[[Category:Computer Science]] | |||
[[Category:Complexity]] | |||
[[Category:Solution]] | |||
[[Category:Instance]] | |||
[[Category:Solving]] | |||
[[Category:Problem]] | |||
Latest revision as of 15:27, 24 December 2023
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