Intermediate Results on the Complexity of STRIPS$_{1}^{1}$

• URL: http://arxiv.org/abs/2602.08708v1
• Date: Mon, 09 Feb 2026 14:21:10 GMT
• Title: Intermediate Results on the Complexity of STRIPS$_{1}^{1}$
• Authors: Stefan Edelkamp, Jiří Fink, Petr Gregor, Anders Jonsson, Bernhard Nebel,
• Abstract summary: It is unknown whether propositional STRIPS with operators that only have one precondition and one effect is NP-complete.<n>We call a SAT solver for small instances, introducing the literal graph, and mapping it to Petri nets.
• Score: 4.706932040794695
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper is based on Bylander's results on the computational complexity of propositional STRIPS planning. He showed that when only ground literals are permitted, determining plan existence is PSPACE-complete even if operators are limited to two preconditions and two postconditions. While NP-hardness is settled, it is unknown whether propositional STRIPS with operators that only have one precondition and one effect is NP-complete. We shed light on the question whether this small solution hypothesis for STRIPS$^1_1$ is true, calling a SAT solver for small instances, introducing the literal graph, and mapping it to Petri nets.

Related papers

• Learning Deterministic Finite-State Machines from the Prefixes of a Single String is NP-Complete [0.0]
  We study the computational complexity of the case where the input sample is prefix-closed.<n>We show that the problem is NP-hard to approximate when the sample set consists of all prefixes of binary strings.
  arXiv  Detail & Related papers  (2026-01-18T23:28:36Z)
• Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations [121.39938773554523]
  The Area Under the ROC Curve (AUC) is a pivotal evaluation metric in real-world scenarios with both class imbalance and decision constraints.<n>We present two simple instance-wise minimax reformulations to close the approximation gap of PAUC optimization.<n>The resulting algorithms enjoy a linear per-iteration computational complexity w.r.t. the sample size and a convergence rate of $O(-2/3)$ for typical one-way and two-way PAUCs.
  arXiv  Detail & Related papers  (2025-12-01T02:52:33Z)
• Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
  We propose two algorithms that enjoy provable scaling laws for the test-time compute of large language models.<n>One is a two-stage knockout-style algorithm, where each candidate is evaluated by its average win rate against multiple opponents.<n>The other is a two-stage league-style algorithm, where each candidate is evaluated by its average win rate against multiple opponents.
  arXiv  Detail & Related papers  (2024-11-29T05:29:47Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Homomorphisms and Embeddings of STRIPS Planning Models [4.594173051888471]
  We show that the first is GI-complete, and can thus be solved, in theory, in quasi-polynomial time. While we prove the remaining problems to be NP-complete, we propose an algorithm to build an isomorphism, when possible.
  arXiv  Detail & Related papers  (2024-06-24T11:43:18Z)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  We revisit the input perturbations framework for differential privacy where noise is added to the input $Ain mathcalS$. We first design novel efficient algorithms to privately release pair-wise cosine similarities. We derive a novel algorithm to compute $k$-way marginal queries over $n$ features.
  arXiv  Detail & Related papers  (2024-06-07T12:07:16Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  Single-Index Models are high-dimensional regression problems with planted structure. We show that computationally efficient algorithms, both within the Statistical Query (SQ) and the Low-Degree Polynomial (LDP) framework, necessarily require $Omega(dkstar/2)$ samples.
  arXiv  Detail & Related papers  (2024-03-08T18:50:19Z)
• Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPs [60.40452803295326]
  We propose a new reward-free algorithm for learning linear Markov decision processes (MDPs) At the core of our algorithm is uncertainty-weighted value-targeted regression with exploration-driven pseudo-reward. We show that our algorithm only needs to explore $tilde O( d2varepsilon-2)$ episodes to find an $varepsilon$-optimal policy.
  arXiv  Detail & Related papers  (2023-03-17T17:53:28Z)
• Simple Binary Hypothesis Testing under Local Differential Privacy and Communication Constraints [8.261182037130407]
  We study simple binary hypothesis testing under both local differential privacy (LDP) and communication constraints. We qualify our results as either minimax optimal or instance optimal.
  arXiv  Detail & Related papers  (2023-01-09T18:36:49Z)
• Semantic Probabilistic Layers for Neuro-Symbolic Learning [83.25785999205932]
  We design a predictive layer for structured-output prediction (SOP) It can be plugged into any neural network guaranteeing its predictions are consistent with a set of predefined symbolic constraints. Our Semantic Probabilistic Layer (SPL) can model intricate correlations, and hard constraints, over a structured output space.
  arXiv  Detail & Related papers  (2022-06-01T12:02:38Z)
• Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiency [111.83670279016599]
  We study reinforcement learning for partially observed decision processes (POMDPs) with infinite observation and state spaces. We make the first attempt at partial observability and function approximation for a class of POMDPs with a linear structure.
  arXiv  Detail & Related papers  (2022-04-20T21:15:38Z)
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers [50.85524803885483]
  This work proposes a formal definition of statistically meaningful (SM) approximation which requires the approximating network to exhibit good statistical learnability. We study SM approximation for two function classes: circuits and Turing machines.
  arXiv  Detail & Related papers  (2021-07-28T04:28:55Z)
• Efficient Explanations With Relevant Sets [30.296628060841645]
  This paper investigates solutions for tackling the practical limitations of $delta$-relevant sets. The computation of the subset of $delta$-relevant sets is in NP, and can be solved with a number of calls to an NP oracle.
  arXiv  Detail & Related papers  (2021-06-01T14:57:58Z)
• A tetrachotomy of ontology-mediated queries with a covering axiom [1.749935196721634]
  Our concern is the problem of efficiently determining the data complexity of answering queries mediated by description and their optimal rewritings to standard database queries. We focus on Boolean conjunctive-mediated queries called disjunctive sirups (or d-sirups) Some d-sirups only have exponential-size resolution features, some only double-exponential-size positive existential existential-rewritings and single-exprecursive datalog rewritings.
  arXiv  Detail & Related papers  (2020-06-07T14:47:07Z)

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.