We explore the complexity of computing the optimal pebbling number and
pebbling number of a graph. We show that deciding whether the optimal pebbling
number of G is at most k is NP-complete and deciding whether the pebbling
number of G is at most k is \Pi_2-complete. Additionally, we provide a
characterization of when an unordered set of pebbling moves can be ordered to
form a valid sequence of pebbling moves.

本文探讨了图的最佳走棋数字和走棋数字的计算复杂性问题，研究表明该问题的决策是 NP - 完全的，并提供了可行的棋步重新排列方案。

图石子游戏的复杂性

The Complexity of Graph Pebbling

The aggregation of conflicting preferences is a central problem in multiagent
systems. The key difficulty is that the agents may report their preferences
insincerely. Mechanism design is the art of designing the rules of the game so
that the agents are motivated to report their preferences truthfully and a
(socially) desirable outcome is chosen. We propose an approach where a
mechanism is automatically created for the preference aggregation setting at
hand. This has several advantages, but the downside is that the mechanism
design optimization problem needs to be solved anew each time. Focusing on
settings where side payments are not possible, we show that the mechanism
design problem is NP-complete for deterministic mechanisms. This holds both for
dominant-strategy implementation and for Bayes-Nash implementation. We then
show that if we allow randomized mechanisms, the mechanism design problem
becomes tractable. In other words, the coordinator can tackle the computational
complexity introduced by its uncertainty about the agents' preferences by
making the agents face additional uncertainty. This comes at no loss, and in
some cases at a gain, in the (social) objective.

本研究探讨了在多智能体系统中，通过机制设计实现代理人诚实报告偏好从而选择出（社会）期望结果的问题。我们提出了一种自动创建偏好聚合机制的方法，并发现在无法进行边际支付的情况下，确定性机制的机制设计问题是 NP 完全的，但随机机制则是可计算的。

机制设计的复杂度

Complexity of Mechanism Design

Describes an algorithm for the generation phase of a Shake-and-Bake Machine
Translation system. Since the problem is NP-complete, it is unlikely that the
algorithm will be efficient in all cases, but for the cases tested it offers an
improvement over Whitelock's previously published algorithm. The work was
carried out while the author was employed at Sharp Laboratories of Europe Ltd.

介绍了一个 Shake-and-Bake 机器翻译系统的生成阶段算法，虽然该问题是 NP 完全问题，算法不可能在所有情况下都高效，但在测试的情况下，它比 Whitelock 先前发表的算法有所改进。该工作是在 Sharp Laboratories of Europe Ltd. 雇员时完成的。