共找到 20 条结果
We show that the metaproblem for coset-generating polymorphisms is NP-complete, answering a question of Chen and Larose: given a finite structure, the computational question is whether this structure has a polymorphism of the form $(x,y,z) \mapsto x y^{-1} z$ with respect to some group; such operations are also called coset-generating, or heaps. Furthermore, we introduce a promise version of the metaproblem, parametrised by two polymorphism conditions $Σ_1$ and $Σ_2$ and defined analogously to the promise constraint satisfaction problem. We give sufficient conditions under which the promise metaproblem for $(Σ_1,Σ_2)$ is in P and under which it is NP-hard. In particular, the promise metaproblem is in P if $Σ_1$ states the existence of a Maltsev polymorphism and $Σ_2$ states the existence of an abelian heap polymorphism -- despite the fact that neither the metaproblem for $Σ_1$ nor the metaproblem for $Σ_2$ is known to be in P. We also show that the creation-metaproblem for Maltsev polymorphisms, under the promise that a heap polymorphism exists, is in P if and only if there is a uniform polynomial-time algorithm for CSPs with a heap polymorphism.
A Boolean predicate $A$ is defined to be promise-useful if $\operatorname{PCSP}(A,B)$ is tractable for some non-trivial $B$ and otherwise it is promise-useless. We initiate investigations of this notion and derive sufficient conditions for both promise-usefulness and promise-uselessness (assuming $\text{P} e \text{NP}$). While we do not obtain a complete characterization, our conditions are sufficient to classify all predicates of arity at most $4$ and almost all predicates of arity $5$. We also derive asymptotic results to show that for large arities a vast majority of all predicates are promise-useless. Our results are primarily obtained by a thorough study of the "Promise-SAT" problem, in which we are given a $k$-SAT instance with the promise that there is a satisfying assignment for which the literal values of each clause satisfy some additional constraint. The algorithmic results are based on the basic LP + affine IP algorithm of Brakensiek et al. (SICOMP, 2020) while we use a number of novel criteria to establish NP-hardness.
I discuss some quantitative representations of Promise Theory for processes involving autonomous agents. Agent models are common in software systems, machine learning, and biology, for example, but may also apply to physics and other forms of engineering. I describe how Bayesian probability and information theoretic optimization, including Active Inference, may be incorporated with promise semantics -- as well as how Promise Theory supplements solutions, helping to avoid probability's pitfalls, which include non-local coordination, calibrating, and normalizing probabilistic computations. The role of boundary conditions in constraining allowed states and selecting decision thresholds is a form of promise, and agent alignment provides a scalable definition of intent. Autonomous agents may congeal into swarms with superagent characteristics by trying to minimize their information, despite uncertainty that works to maximize it. The use of Promise Theory involves some research challenges as well as stylistic preferences.
Promises made by politicians, corporate leaders, and public figures have a significant impact on public perception, trust, and institutional reputation. However, the complexity and volume of such commitments, coupled with difficulties in verifying their fulfillment, necessitate innovative methods for assessing their credibility. This paper introduces the concept of Promise Verification, a systematic approach involving steps such as promise identification, evidence assessment, and the evaluation of timing for verification. We propose the first multilingual dataset, ML-Promise, which includes English, French, Chinese, Japanese, and Korean, aimed at facilitating in-depth verification of promises, particularly in the context of Environmental, Social, and Governance (ESG) reports. Given the growing emphasis on corporate environmental contributions, this dataset addresses the challenge of evaluating corporate promises, especially in light of practices like greenwashing. Our findings also explore textual and image-based baselines, with promising results from retrieval-augmented generation (RAG) approaches. This work aims to foster further discourse on the accountability of public commitme
Automated proof generation for formal software verification remains largely unresolved despite advances in large language models (LLMs). While LLMs perform well in NLP, vision, and code generation, formal verification still requires substantial human effort. Interactive theorem proving (ITP) demands manual proof construction under strict logical constraints, limiting scalability; for example, verifying the seL4 microkernel required decades of effort. Existing LLM-based approaches attempt to automate this process but remain limited. Most rely on single-shot generation or shallow retrieval, which may work for small proofs but fail to scale to large, interdependent verification tasks with deep structural dependencies. We present PROMISE (PROof MIning via Structural Embeddings), a structure-aware framework that reframes proof generation as a stateful search over proof-state transitions. Instead of surface-level retrieval, PROMISE mines structural patterns from proof states and tactic transitions, enabling retrieval and adaptation of compatible proof fragments during iterative search. We evaluate PROMISE on the seL4 benchmark across multiple LLM backends and compare it with prior system
A unique sink orientation (USO) is an orientation of the edges of a hypercube such that each face has a unique sink. Many optimization problems like linear programs reduce to USOs, in the sense that each vertex corresponds to a possible solution, and the global sink corresponds to the optimal solution. People have been studying intensively the problem of find the sink of a USO using vertex evaluations, i.e., queries which return the orientation of the edges around a vertex. This problem is a so called promise problem, as it assumes that the orientation it receives is a USO. In this paper, we analyze a non-promise version of the USO problem, in which we try to either find a sink or an efficiently verifiable violation of the USO property. This problem is worth investigating, because some problems which reduce to USO are also promise problems (and so we can also define a non-promise version for them), and it would be interesting to discover where USO lies in the hierarchy of subclasses of $\texttt{TFNP}^\texttt{dt}$, and for this a total search problem is required (which is the case for the non-promise version). We adapt many known properties and algorithms from the promise version to
Computing the convex hull of a planar $n$-point set $P$ is one of the most fundamental problems in computational geometry. It has an $Ω(n \log n)$ lower bound in the algebraic computation tree model, and many convex hull algorithms match this bound. Classical results show that, under special input assumptions, sub-$O(n \log n)$ algorithms are possible. For instance, when the points are given in lexicographic or angular order, the convex hull can be computed in linear time. Even under the weaker assumption that the sequence of points corresponds to the ordered vertices of a simple polygonal chain, linear-time algorithms exist. This naturally raises the question: can the convex hull of a point set be computed in sub-$O(n \log n)$ time under weaker input assumptions? We answer this positively. Under the promise that the input sequence contains the convex hull as a subsequence, we give a deterministic $O(n \sqrt{\log n})$-time algorithm to compute the convex hull of $P$. With randomisation, we achieve expected running time $O(n \log^{\varepsilon} n)$ for any constant $\varepsilon > 0$. We find this surprising, as points not on the convex hull may behave adversarially toward our conv
Given two $m$-ary predicates $P,Q$, an $n$-ary polymorphism is a tuple $(f_1,\dots,f_m)$ of functions such that $x^{(1)},\dots,x^{(n)} \in P$ implies $(f_1(y_1),\dots,f_m(y_m)) \in Q$, where $y_i = (x^{(1)}_i,\dots,x^{(m)}_i)$. This generalizes the usual definition in universal algebra, in which $P = Q$ and $f_1 = \cdots = f_m$. In earlier work, we studied when all polymorphisms of a single predicate are "trivial": either all depend on a single coordinate (common to all of them), or they constitute a "certificate" for the predicate. We showed that it suffices to check this condition for $2$-ary polymorphisms, and even for $1$-ary polymorphisms, modulo an explicit list of obstructions. In this paper we generalize the first result to the $P,Q$ setting, for a relaxed notion of certificate. We also generalize the second result in the promise setting, in which $P,Q$ range over the same alphabets and $P \subseteq Q$.
Agent based systems are more common than we may think. A Promise Theory perspective on cooperation, in systems of human-machine agents, offers a unified perspective on organization and functional design with semi-automated efforts, in terms of the abstract properties of autonomous agents, This applies to human efforts, hardware systems, software, and artificial intelligence, with and without management. One may ask how does a reasoning system of components keep to an intended purpose? As the agent paradigm is now being revived, in connection with artificial intelligence agents, I revisit established principles of agent cooperation, as applied to humans, machines, and their mutual interactions. Promise Theory represents the fundamentals of signalling, comprehension, trust, risk, and feedback between agents, and offers some lessons about success and failure.
How can voters induce politicians to put forth more proximate (in terms of preference) as well as credible platforms (in terms of promise fulfillment) under repeated elections? Building on the work of Aragones et al. (2007), I study how reputation and re-election concerns affect candidate behavior and its resultant effect on voters' beliefs and their consequent electoral decisions. I present a formal model where, instead of assuming voters to be naive, I tackle the question by completely characterizing a set of subgame-perfect equilibria by introducing non-naive (or strategic) voting behavior into the mix. I find that non-naive voting behavior, by using the candidate's reputation as an instrument of policy discipline after the election, aids in successfully inducing candidates to put forth their maximal incentive-compatible promise (among a range of such credible promises) in equilibrium. Through the credible threat of punishment in the form of loss of reputation for all future elections, non-naive voters gain a unanimous increase in expected utility relative to when they behave naively. In fact, comparative statics show that candidates who are more likely to win are more likely to
Despite growing evidence that neighborhoods play a critical role in shaping economic mobility and well-being, effective policies to address neighborhood disadvantage remain elusive. This study evaluates the impact of the Promise Zone program, which aims to revitalize disadvantaged neighborhoods through streamlined federal support and grant incentives. I use an event study framework with newly obtained data on the location of failed finalist applications as a comparison group to estimate the effects of the program. The results reveal significant improvements in poverty, household incomes, and employment in Promise Zone neighborhoods, particularly in later-designated zones and initially low-status neighborhoods. I also find that effects are driven partly by changes in residential composition, and that Promise Zones appear to induce positive spillovers in adjacent areas.
We establish a framework that allows us to transfer results between some constraint satisfaction problems with infinite templates and promise constraint satisfaction problems. On the one hand, we obtain new algebraic results for infinite-domain CSPs giving new criteria for NP-hardness. On the other hand, we show the existence of promise CSPs with finite templates that reduce naturally to tractable infinite-domain CSPs within the scope of the Bodirsky-Pinsker conjecture, but that are not finitely tractable, thereby showing a non-trivial connection between those two fields of research. In an important part of our proof, we also obtain uniform polynomial-time algorithms solving temporal constraint satisfaction problems.
The polynomial hierarchy is a grading of problems by difficulty, including P, NP and coNP as the best known classes. The promise polynomial hierarchy is similar, but extended to include promise problems. It turns out that the promise polynomial hierarchy is considerably simpler to work with, and many open questions about the polynomial hierarchy can be resolved in the promise polynomial hierarchy. Our main theorem is that, in the world of promise problems, if phi has a weak (Turing, Cook) reduction to SAT then phi has a strong (Karp, many-one) reduction to UVAL2, where UVAL2(f) is the promise problem of finding the unique x such that f(x,y)=1 for all y. We also give a complete promise problem for the promise problem equivalent of UP intersect coUP.
We present a simple argument using Promise Theory and dimensional analysis for the Dunbar scaling hierarchy, supported by recent data from group formation in Wikipedia editing. We show how the assumption of a common priority seeds group alignment until the costs associated with attending to the group outweigh the benefits in a detailed balance scenario. Subject to partial efficiency of implementing promised intentions, we can reproduce a series of compatible rates that balance growth with entropy.
The concept of promise problems was introduced and started to be systematically explored by Even, Selman, Yacobi, Goldreich, and other scholars. It has been argued that promise problems should be seen as partial decision problems and as such that they are more fundamental than decision problems and formal languages that used to be considered as the basic ones for complexity theory. The main purpose of this paper is to explore the promise problems accepted by classical, quantum and also semi-quantum finite automata. More specifically, we first introduce two acceptance modes of promise problems, recognizability and solvability, and explore their basic properties. Afterwards, we show several results concerning descriptional complexity on promise problems. In particular, we prove: (1) there is a promise problem that can be recognized exactly by measure-once one-way quantum finite automata (MO-1QFA), but no deterministic finite automata (DFA) can recognize it; (2) there is a promise problem that can be solved with error probability $ε\leq 1/3$ by one-way finite automaton with quantum and classical states (1QCFA), but no one-way probability finite automaton (PFA) can solve it with error
The study of the complexity of the constraint satisfaction problem (CSP), centred around the Feder-Vardi Dichotomy Conjecture, has been very prominent in the last two decades. After a long concerted effort and many partial results, the Dichotomy Conjecture has been proved in 2017 independently by Bulatov and Zhuk. At about the same time, a vast generalisation of CSP, called promise CSP, has started to gain prominence. In this survey, we explain the importance of promise CSP and highlight many new very interesting features that the study of promise CSP has brought to light. The complexity classification quest for the promise CSP is wide open, and we argue that, despite the promise CSP being more general, this quest is rather more accessible to a wide range of researchers than the dichotomy-led study of the CSP has been.
Task-parallel programs often enjoy deadlock freedom under certain restrictions, such as the use of structured join operations, as in Cilk and X10, or the use of asynchronous task futures together with deadlock-avoiding policies such as Known Joins or Transitive Joins. However, the promise, a popular synchronization primitive for parallel tasks, does not enjoy deadlock-freedom guarantees. Promises can exhibit deadlock-like bugs; however, the concept of a deadlock is not currently well-defined for promises. To address these challenges, we propose an ownership semantics in which each promise is associated to the task which currently intends to fulfill it. Ownership immediately enables the identification of bugs in which a task fails to fulfill a promise for which it is responsible. Ownership further enables the discussion of deadlock cycles among tasks and promises and allows us to introduce a robust definition of deadlock-like bugs for promises. Cycle detection in this context is non-trivial because it is concurrent with changes in promise ownership. We provide a lock-free algorithm for precise runtime deadlock detection. We show how to obtain the memory consistency criteria required
The quantum switch is a quantum computational primitive that provides computational advantage by applying operations in a superposition of orders. In particular, it can reduce the number of gate queries required for solving promise problems where the goal is to discriminate between a set of properties of a given set of unitary gates. In this work, we use Complex Hadamard matrices to introduce more general promise problems, which reduce to the known Fourier and Hadamard promise problems as limiting cases. Our generalization loosens the restrictions on the size of the matrices, number of gates and dimension of the quantum systems, providing more parameters to explore. In addition, it leads to the conclusion that a continuous variable system is necessary to implement the most general promise problem. In the finite dimensional case, the family of matrices is restricted to the so-called Butson-Hadamard type, and the complexity of the matrix enters as a constraint. We introduce the ``query per gate'' parameter and use it to prove that the quantum switch provides computational advantage for both the continuous and discrete cases. Our results should inspire implementations of promise probl
Promise CSPs are a relaxation of constraint satisfaction problems where the goal is to find an assignment satisfying a relaxed version of the constraints. Several well-known problems can be cast as promise CSPs including approximate graph coloring, discrepancy minimization, and interesting variants of satisfiability. Similar to CSPs, the tractability of promise CSPs can be tied to the structure of operations on the solution space called polymorphisms, though in the promise world these operations are much less constrained. Under the thesis that non-trivial polymorphisms govern tractability, promise CSPs therefore provide a fertile ground for the discovery of novel algorithms. In previous work, we classified Boolean promise CSPs when the constraint predicates are symmetric. In this work, we vastly generalize these algorithmic results. Specifically, we show that promise CSPs that admit a family of "regional-periodic" polymorphisms are in P, assuming that determining which region a point is in can be computed in polynomial time. Such polymorphisms are quite general and are obtained by gluing together several functions that are periodic in the Hamming weights in different blocks of the
The advent of increasingly powerful language models has raised expectations for language-based interactions. However, controlling these models is a challenge, emphasizing the need to be able to investigate the feasibility and value of their application. We present PROMISE, a framework that facilitates the development of complex language-based interactions with information systems. Its use of state machine modeling concepts enables model-driven, dynamic prompt orchestration across hierarchically nested states and transitions. This improves the control of the behavior of language models and thus enables their effective and efficient use. In this technical report we show the benefits of PROMISE in the context of application scenarios within health information systems and demonstrate its ability to handle complex interactions. We also include code examples and present default user interfaces available as part of PROMISE.