Proof systems that take advice

One of the starting points of propositional proof complexity is the seminal paper by Cook and Reckhow [J. Symbolic Logic, 1979], where they defined propositional proof systems as poly-time computable functions which have all propositional tautologies as their range. Motivated by provability consequences in bounded arithmetic, Cook and Kraj?´?ek [J. Symbolic Logic, 2007] have recently started the investigation of proof systems which are computed by poly-time functions using advice.In this paper we concentrate on three fundamental questions regarding this new model. First, we investigate whether a given language L admits a polynomially bounded proof system with advice. Depending on the complexity of the underlying language L and the amount and type of the advice used by the proof system, we obtain different characterizations for this problem. In particular, we show that this question is tightly linked with the question whether L has small nondeterministic instance complexity.The second question concerns the existence of optimal proof systems with advice. For propositional proof systems, Cook and Kraj?´?ek gave a surprising positive answer which we extend to all languages.These results show that providing proof systems with advice yields a more powerful model, but this model is also less directly applicable in practice. Our third question therefore asks whether the usage of advice in propositional proof systems can be simplified or even eliminated. While in principle, the advice can be very complex, we show that propositional proof systems with logarithmic advice are also computable in poly-time with access to a sparse NP-oracle. Employing a recent technique of Buhrman and Hitchcock [CCC, 2008] we also manage to transfer the advice from the proof to the proven formula, which leads to a more practical computational model.     

A direct construction of polynomial-size OBDD proof of pigeon hole problem

Viewing OBDD from the explicit perspective of a propositional proof system is first proposed and studied in [A. Atserias, P.G. Kolaitis, M.Y. Vardi, Constraint propagation as a proof system, in: CP, 2004, pp. 77-91]. It has been shown that OBDD proof system defined in [A. Atserias, P.G. Kolaitis, M.Y. Vardi, Constraint propagation as a proof system, in: CP, 2004, pp. 77-91] is strictly stronger than resolution and can polynomially simulate cutting plane proof system with small coefficients CP^∗. It is already shown in [W. Cook, C.R. Coullard, G. Turán, On the complexity of cutting-plane proofs, Discrete Appl. Math. 18 (1) (1987) 25-38] that there exists polynomial-size proof for pigeon hole problem of cutting plane proof system. Then it follows directly that there exists polynomial-size proof for of OBDD proof system. However, this is an indirect result. Atserias et al. [A. Atserias, P.G. Kolaitis, M.Y. Vardi, Constraint propagation as a proof system, in: CP, 2004, pp. 77-91] call for the need of a direct construction. Hereby we present such construction. Moreover, in this construction we do not need the weakening rule introduced in [A. Atserias, P.G. Kolaitis, M.Y. Vardi, Constraint propagation as a proof system, in: CP, 2004, pp. 77-91]. We believe this may shed some light on the understanding of the role of the weakening rule.     

What makes propositional abduction tractable

Abduction is a fundamental form of nonmonotonic reasoning that aims at finding explanations for observed manifestations. This process underlies many applications, from car configuration to medical diagnosis. We study here the computational complexity of deciding whether an explanation exists in the case when the application domain is described by a propositional knowledge base. Building on previous results, we classify the complexity for local restrictions on the knowledge base and under various restrictions on hypotheses and manifestations. In comparison to the many previous studies on the complexity of abduction we are able to give a much more detailed picture for the complexity of the basic problem of deciding the existence of an explanation. It turns out that depending on the restrictions, the problem in this framework is always polynomial-time solvable, NP-complete, coNP-complete, or -complete.

Based on these results, we give an a posteriori justification of what makes propositional abduction hard even for some classes of knowledge bases which allow for efficient satisfiability testing and deduction. This justification is very simple and intuitive, but it reveals that no nontrivial class of abduction problems is tractable. Indeed, tractability essentially requires that the language for knowledge bases is unable to express both causal links and conflicts between hypotheses. This generalizes a similar observation by Bylander et al. for set-covering abduction.     

Mutilated chessboard problem is exponentially hard for resolution

Mutilated chessboard principle CB_n says that it is impossible to cover by domino tiles the chessboard 2n×2n with two diagonally opposite corners removed. We prove lower bound on the size of minimal resolution refutation of CB_n.     

The complexity of propositional implication

The question whether a set of formulae Γ implies a formula φ is fundamental. The present paper studies the complexity of the above implication problem for propositional formulae that are built from a systematically restricted set of Boolean connectives. We give a complete complexity-theoretic classification for all sets of Boolean functions in the meaning of Post's lattice and show that the implication problem is efficiently solvable only if the connectives are definable using the constants {0,1} and only one of {∧,∨,⊕}. The problem remains coNP-complete in all other cases. We also consider the restriction of Γ to singletons which makes the problem strictly easier in some cases.     

Redundancy in logic I: CNF propositional formulae

A knowledge base is redundant if it contains parts that can be inferred from the rest of it. We study some problems related to the redundancy of a CNF formula. In particular, any CNF formula can be made irredundant by deleting some of its clauses: what results is an irredundant equivalent subset. We study the complexity of problems related to irredundant equivalent subsets: verification, checking existence of an irredundant equivalent subset with a given size, checking necessary and possible presence of clauses in irredundant equivalent subsets, and uniqueness. We also consider the problem of redundancy with different definitions of equivalence.     

Non-Automatizability of Bounded-Depth Frege Proofs

In this paper, we show how to extend the argument due to Bonet, Pitassi and Raz to show that bounded-depth Frege proofs do not have feasible interpolation, assuming that factoring of Blum integers or computing the Diffie–Hellman function is sufficiently hard. It follows as a corollary that bounded-depth Frege is not automatizable; in other words, there is no deterministic polynomial-time algorithm that will output a short proof if one exists. A notable feature of our argument is its simplicity.     

Proof Complexity of the Cut-free Calculus of Structures

We investigate the proof complexity of analytic subsystems ofthe deep inference proof system SKSg (the calculus of structures).Exploiting the fact that the cut rule (i) of SKSg correspondsto the ¬-left rule in the sequent calculus, we establishthat the ‘analytic'system KSg+c has essentially the samecomplexity as the monotone Gentzen calculus MLK. In particular,KSg+c quasipolynomially simulates SKSg, and admits polynomial-sizeproofs of some variants of the pigeonhole principle.     

Parallelization of entanglement-resistant multi-prover interactive proofs

Multi-prover interactive proof systems are said to be entanglement-resistant if the soundness holds even when provers are allowed to share an arbitrary quantum state before the interaction starts. This letter proves that every entanglement-resistant multi-prover interactive proof system can be parallelized to two rounds without ruining its entanglement resistance at the expense of adding one prover.     

基于独立集问题的零知识证明研究

零知识证明已经成为信息安全领域身份认证的关键技术之一。为了避免已知零知识证明系统的图同构问题,提出了一种知识的计算零知识证明系统,其安全性建立在NPC独立集问题上。该算法的构造基于离散对数问题的困难性,从而保证了系统的合理性、完全性、计算零知识性。并从计算复杂度和通信复杂度两方面对系统及其算法参数的选取进行了分析。理论证明,该系统是可行有效的。     

Isomorphic Implication

We study the isomorphic implication problem for Boolean constraints. We show that this is a natural analog of the subgraph isomorphism problem. We prove that, depending on the set of constraints, this problem is in P, or is NP-complete, or is NP-hard, coNP-hard, and in P_‖^NP. We show how to extend the NP-hardness and coNP-hardness to P_‖^NP-hardness for some cases, and conjecture that this can be done in all cases. Supported in part by grants NSF-CCR-0311021 and DFG VO 630/5-1 and VO 630/5-2. An extended abstract of this paper appears in Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science (MFCS 2005), pp. 119–130, Springer-Verlag Lecture Notes in Computer Science #3618, August 2005. Work of M. Bauland done in part while visiting CASCI’s Laboratory for Complexity at Rochester Institute of Technology. Work of E. Hemaspaandra done in part while on sabbatical at the University of Rochester.     

基于独立集问题的零知识证明研究

零知识证明已经成为信息安全领域身份认证的关键技术之一。为了避免已知零知识证明系统的图同构问题，提出了一种知识的计算零知识证明系统，其安全性建立在NPC独立集问题上。该算法的构造基于离散对数问题的困难性，从而保证了系统的合理性、完全性、计算零知识性。并从计算复杂度和通信复杂度两方面对系统及其算法参数的选取进行了分析。理论证明，该系统是可行有效的。     

On the computational complexity of qualitative coalitional games

We study coalitional games in which agents are each assumed to have a goal to be achieved, and where the characteristic property of a coalition is a set of choices, with each choice denoting a set of goals that would be achieved if the choice was made. Such qualitative coalitional games (qcgs) are a natural tool for modelling goal-oriented multiagent systems. After introducing and formally defining qcgs, we systematically formulate fourteen natural decision problems associated with them, and determine the computational complexity of these problems. For example, we formulate a notion of coalitional stability inspired by that of the core from conventional coalitional games, and prove that the problem of showing that the core of a qcg is non-empty is D^p₁-complete. (As an aside, we present what we believe is the first “natural” problem that is proven to be complete for D^p₂.) We conclude by discussing the relationship of our work to other research on coalitional reasoning in multiagent systems, and present some avenues for future research.     

Model Checking Abilities of Agents: A Closer Look

Alternating-time temporal logic (atl) is a logic for reasoning about open computational systems and multi-agent systems. It is well known that atl model checking is linear in the size of the model. We point out, however, that the size of an atl model is usually exponential in the number of agents. When the size of models is defined in terms of states and agents rather than transitions, it turns out that the problem is (1) Δ ₃ ^P -complete for concurrent game structures, and (2) Δ ₂ ^P -complete for alternating transition systems. Moreover, for “Positive atl” that allows for negation only on the level of propositions, model checking is (1) Σ ₂ ^P -complete for concurrent game structures, and (2) NP-complete for alternating transition systems. We show a nondeterministic polynomial reduction from checking arbitrary alternating transition systems to checking turn-based transition systems, We also discuss the determinism assumption in alternating transition systems, and show that it can be easily removed. In the second part of the paper, we study the model checking complexity for formulae of atl with imperfect information (atl _ir ). We show that the problem is Δ ₂ ^P -complete in the number of transitions and the length of the formula (thereby closing a gap in previous work of Schobbens in Electron. Notes Theor. Comput. Sci. 85(2), 2004). Then, we take a closer look and use the same fine structure complexity measure as we did for atl with perfect information. We get the surprising result that checking formulae of atl _ir is also Δ ₃ ^P -complete in the general case, and Σ ₂ ^P -complete for “Positive atl _ir ”. Thus, model checking agents’ abilities for both perfect and imperfect information systems belongs to the same complexity class when a finer-grained analysis is used.     

Transversal of disjoint convex polygons

Given a set S of n disjoint convex polygons {P_i∣1?i?n} in a plane, each with k_i vertices, the transversal problem is to find, if there exists one, a straight line that goes through every polygon in S. We show that the transversal problem can be solved in O(N+nlogn) time, where N=∑_i=1ⁿk_i is the total number of vertices of the polygons.