Characterizing Structural Hardness of Logic Programs: What makes Cycles and Reachability Hard for Treewidth?

• URL: http://arxiv.org/abs/2301.07472v1
• Date: Wed, 18 Jan 2023 12:29:45 GMT
• Title: Characterizing Structural Hardness of Logic Programs: What makes Cycles and Reachability Hard for Treewidth?
• Authors: Markus Hecher
• Abstract summary: This paper deals with a novel reduction from SAT to normal ASP that goes beyond well-known encodings. This characterizes hardness in a fine-grained way by establishing the required functional dependency of the dependency graph's cycle length.
• Score: 9.480212602202517
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Answer Set Programming (ASP) is a problem modeling and solving framework for several problems in KR with growing industrial applications. Also for studies of computational complexity and deeper insights into the hardness and its sources, ASP has been attracting researchers for many years. These studies resulted in fruitful characterizations in terms of complexity classes, fine-grained insights in form of dichotomy-style results, as well as detailed parameterized complexity landscapes. Recently, this lead to a novel result establishing that for the measure treewidth, which captures structural density of a program, the evaluation of the well-known class of normal programs is expected to be slightly harder than deciding satisfiability (SAT). However, it is unclear how to utilize this structural power of ASP. This paper deals with a novel reduction from SAT to normal ASP that goes beyond well-known encodings: We explicitly utilize the structural power of ASP, whereby we sublinearly decrease the treewidth, which probably cannot be significantly improved. Then, compared to existing results, this characterizes hardness in a fine-grained way by establishing the required functional dependency of the dependency graph's cycle length (SCC size) on the treewidth.

Related papers

• AUCSeg: AUC-oriented Pixel-level Long-tail Semantic Segmentation [88.50256898176269]
  We develop a pixel-level AUC loss function and conduct a dependency-graph-based theoretical analysis of the algorithm's generalization ability. We also design a Tail-Classes Memory Bank to manage the significant memory demand.
  arXiv  Detail & Related papers  (2024-09-30T15:31:02Z)
• Enhancing Systematic Decompositional Natural Language Inference Using Informal Logic [51.967603572656266]
  We introduce a consistent and theoretically grounded approach to annotating decompositional entailment. We find that our new dataset, RDTE, has a substantially higher internal consistency (+9%) than prior decompositional entailment datasets. We also find that training an RDTE-oriented entailment classifier via knowledge distillation and employing it in an entailment tree reasoning engine significantly improves both accuracy and proof quality.
  arXiv  Detail & Related papers  (2024-02-22T18:55:17Z)
• Extended Version of: On the Structural Hardness of Answer Set Programming: Can Structure Efficiently Confine the Power of Disjunctions? [21.10339925217772]
  We deal with the classification of structural parameters for disjunctive ASP on the program's rule structure. We provide double-exponential lower bounds for the most prominent parameters in that range. Our results provide an in-depth hardness study, relying on a novel reduction from normal to disjunctive programs.
  arXiv  Detail & Related papers  (2024-02-05T21:51:36Z)
• When Do Program-of-Thoughts Work for Reasoning? [51.2699797837818]
  We propose complexity-impacted reasoning score (CIRS) to measure correlation between code and reasoning abilities. Specifically, we use the abstract syntax tree to encode the structural information and calculate logical complexity. Code will be integrated into the EasyInstruct framework at https://github.com/zjunlp/EasyInstruct.
  arXiv  Detail & Related papers  (2023-08-29T17:22:39Z)
• SE-GSL: A General and Effective Graph Structure Learning Framework through Structural Entropy Optimization [67.28453445927825]
  Graph Neural Networks (GNNs) are de facto solutions to structural data learning. Existing graph structure learning (GSL) frameworks still lack robustness and interpretability. This paper proposes a general GSL framework, SE-GSL, through structural entropy and the graph hierarchy abstracted in the encoding tree.
  arXiv  Detail & Related papers  (2023-03-17T05:20:24Z)
• Treewidth-aware Reductions of Normal ASP to SAT -- Is Normal ASP Harder than SAT after All? [9.480212602202517]
  We show a new result establishing that, when considering treewidth, already the fragment of normal ASP is slightly harder than SAT. We present an empirical study of our novel reduction from normal ASP to SAT, where we compare treewidth upper bounds that are obtained via known decompositions.
  arXiv  Detail & Related papers  (2022-10-07T13:40:07Z)
• Provable Reinforcement Learning with a Short-Term Memory [68.00677878812908]
  We study a new subclass of POMDPs, whose latent states can be decoded by the most recent history of a short length $m$. In particular, in the rich-observation setting, we develop new algorithms using a novel "moment matching" approach with a sample complexity that scales exponentially. Our results show that a short-term memory suffices for reinforcement learning in these environments.
  arXiv  Detail & Related papers  (2022-02-08T16:39:57Z)
• Learning Bayesian Networks in the Presence of Structural Side Information [22.734574764075226]
  We study the problem of learning a Bayesian network (BN) of a set of variables when structural side information about the system is available. We develop an algorithm that efficiently incorporates such knowledge into the learning process. As a consequence of our work, we show that bounded treewidth BNs can be learned with complexity.
  arXiv  Detail & Related papers  (2021-12-20T22:14:19Z)
• Efficient Micro-Structured Weight Unification and Pruning for Neural Network Compression [56.83861738731913]
  Deep Neural Network (DNN) models are essential for practical applications, especially for resource limited devices. Previous unstructured or structured weight pruning methods can hardly truly accelerate inference. We propose a generalized weight unification framework at a hardware compatible micro-structured level to achieve high amount of compression and acceleration.
  arXiv  Detail & Related papers  (2021-06-15T17:22:59Z)
• Efficient and Scalable Structure Learning for Bayesian Networks: Algorithms and Applications [33.8980356362084]
  We propose a new structure learning algorithm, LEAST, which comprehensively fulfills our business requirements. LEAST is deployed and serves for more than 20 applications with thousands of executions per day. We show that LEAST unlocks the possibility of applying BN structure learning in new areas, such as large-scale gene expression data analysis and explainable recommendation system.
  arXiv  Detail & Related papers  (2020-12-07T09:11:08Z)
• Structural Decompositions of Epistemic Logic Programs [29.23726484912091]
  Epistemic logic programs (ELPs) are a popular generalization of standard Answer Set Programming (ASP) We show that central problems can be solved in linear time for ELPs exhibiting structural properties in terms of bounded treewidth. We also provide a full dynamic programming algorithm that adheres to these bounds.
  arXiv  Detail & Related papers  (2020-01-13T13:16:13Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.