obstinate
发表于 2025-3-23 11:45:23
The Boolean Hierarchy of NP-Partitions,. Whereas the structure of the latter hierarchy is rather simple the structure of the boolean hierarchy of .-partitions over NP for . ≥ 3 turns out to be much more complicated. We establish the Embedding Conjecture which enables us to get a complete idea of this structure. This conjecture is supported by several partial results.
组成
发表于 2025-3-23 14:11:17
http://reply.papertrans.cn/87/8604/860323/860323_12.png
起波澜
发表于 2025-3-23 20:05:09
http://reply.papertrans.cn/87/8604/860323/860323_13.png
licence
发表于 2025-3-24 01:29:15
http://reply.papertrans.cn/87/8604/860323/860323_14.png
使熄灭
发表于 2025-3-24 03:23:47
Average-Case Quantum Query Complexity,assical algorithms. Under non-uniform distributions the gap can even be super-exponential. We also prove some general bounds for average-case complexity and show that the average-case quantum complexity of MAJORITY under the uniform distribution is nearly quadratically better than the classical complexity.
Ebct207
发表于 2025-3-24 07:40:13
Bias Invariance of Small Upper Spans,ed upwards.) The proof introduces two new techniques, namely, the . of a martingale for one probability measure to a martingale for an induced probability measure, and a new, improved . of one bias sequence to another. Consequences for the BPP versus E problem and small span theorems are derived.
HERTZ
发表于 2025-3-24 12:35:35
Succinct Representations of Model Based Belief Revision,ly, we show that Dalal’s and Weber’s operators can be compiled one into the other via a formalism whose model checking is in NP. All of our results also hold when iterated revision, for one or more of the operators, is considered.
天真
发表于 2025-3-24 17:33:06
http://reply.papertrans.cn/87/8604/860323/860323_18.png
congenial
发表于 2025-3-24 20:25:01
About Cube-Free Morphisms,unpublished result of Leconte: A binary morphism is cube-free if and only if the images of all cube-free words of length 7 are cube-free..We also prove that, given an alphabet . containing at least two letters, the monoid of cube-free endomorphisms on . is not finitely generated.
occurrence
发表于 2025-3-25 03:02:15
The Data Broadcast Problem with Preemption,ed. We show that this problem is .-hard, even in the simple setting where the broadcast costs are zero, and give some practical 2-approximation algorithms for broadcasting messages. We also show that preemption can improve the quality of the broadcast by an arbitrary factor.