Searching for circles of pure proofs

When given a set of properties or conditions (say, three) that are claimed to be equivalent, the claim can be verified by supplying what we call acircle of proofs. In the case in point, one proves the second property or condition from the first, the third from the second, and the first from the third. If the proof that 1 implies 2 does not rely on 3, then we say that the proof is pure with respect to 3, or simply say theproof is pure. If one can renumber the three properties or conditions in such a way that one can find a circle of three pure proofs — technically, each proof pure with respect to the condition that is neither the hypothesis nor the conclusion — then we say that acircle of pure proofs has been found. Here we study the specific question of the existence of a circle of pure proofs for the thirteen shortest single axioms for equivalential calculus, subject to the requirement that condensed detachment be used as the rule of inference. For an indication of the difficulty of answering the question, we note that a single application of condensed detachment to the (shortest single) axiom known asP4 (also known asUM) with itself yields the (shortest single) axiomP5 (also known asXGF), and two applications of condensed detachment beginning withP5 as hypothesis yieldsP4. Therefore, except forP5, one cannot find a pure proof of any of the twelve shortest single axioms when usingP4 as hypothesis or axiom, for the first application of condensed detachment must focus on two copies ofP4, which results in the deduction ofP5, forcingP5 to be present in all proofs that useP4 as the only axiom. Further, the close proximity in the proof sense ofP4 when using as the only axiomP5 threatens to make impossible the discovery of a circle of pure proofs for the entire set of thirteen shortest single axioms. Perhaps more important than our study of pure proofs, and of a more general nature, we also present the methodology used to answer the cited specific question, a methodology that relies on various strategies and features offered by W. McCune's automated reasoning programOtter. The strategies and features ofOtter we discuss here offer researchers the needed power to answer deep questions and solve difficult problems. We close this article (in the last two sections) with some challenges and some topics for research and (in the Appendix) with a sample input file and some proofs for study.Author supported by the Mathematical, Information, and Computational Sciences Division, Subprogram of the Office of Computational and Technology Research, U.S. Department of Energy, under Contract W-31-109-Eng-38.     

Round-optimal zero-knowledge proofs of knowledge for NP

It is well known that all the known black-box zero-knowledge proofs of knowledge for NP are nonconstant-round.Whether there exit constant-round black-box zero-knowledge proofs of knowledge for all NP languages under certain standard assumptions is an open problem.This paper focuses on the problem and gives a positive answer by presenting two constructions of constant-round(black-box) zero-knowledge proofs of knowledge for the HC(hamiltonian cycle) problem.By the recent result of Katz,our second construction which relies on the existence of claw-free functions has optimal round complexity(5-round) assuming the polynomial hierarchy does not collapse.     

NP问题的最优轮复杂性知识的零知识证明

NP问题已有的知识的(黑箱)零知识证明都是非常数轮的,因此,在标准的复杂性假设下,NP问题是否存在常数轮的(黑箱)知识的零知识证明是一个有意义的问题.本文对该问题进行了研究,在一定的假设下给出了HC问题的两个常数轮知识的零知识证明系统.根据Katz最近的研究结果,在多项式分层不坍塌的条件下,本文基于claw-free陷门置换给出的HC问题的5轮知识的零知识证明系统具有最优的轮复杂性.     

Width versus size in resolution proofs

A general theme in the proof of lower bounds on the size of resolution refutations in propositional logic has been that of basing size lower bounds on lower bounds on the width of refutations. Ben-Sasson and Wigderson have proved a general width-size tradeoff result that can be used to prove many of the lower bounds on resolution complexity in a uniform manner. However, it does not apply directly to the well known pigeonhole clauses. The present paper generalizes their width-size tradeoff so that it applies directly to (a monotone transformation of) the pigeonhole clauses.     

Automated compositional proofs for real-time systems

We present a framework for formally proving that the composition of the behaviors of the different parts of a complex, real-time system ensures a desired global specification of the overall system. The framework is based on a simple compositional rely/guarantee circular inference rule, plus a methodology concerning the integration of the different parts into a whole system. The reference specification language is the TRIO metric linear temporal logic.     

Constant-round zero-knowledge proofs of knowledge with strict polynomial-time extractors for NP

Barak and Lindell showed that there exist constant-round zero-knowledge arguments of knowledge with strict polynomial-time extractors.This leaves the open problem of whether it is possible to obtain an analogous result regarding constant-round zero-knowledge proofs of knowledge for NP.This paper focuses on this problem and gives a positive answer by presenting a construction of constant-round zero-knowledge proofs of knowledge with strict polynomial-time extractors for NP.     

Complexity of Positivstellensatz proofs for the knapsack

A lower bound is established on degrees of Positivstellensatz calculus refutations (over a real field) introduced in (Grigoriev & Vorobjov 2001; Grigoriev 2001) for the knapsack problem. The bound depends on the values of coefficients of an instance of the knapsack problem: for certain values the lower bound is linear and for certain values the upper bound is constant, while in the polynomial calculus the degree is always linear (regardless of the values of coefficients) (Impagliazzo et al. 1999). This shows that the Positivstellensatz calculus can be strictly stronger than the polynomial calculus from the point of view of the complexity of the proofs. Received: February 9, 2000.     

Writing programs that construct proofs

When we learn mathematics, we learn more than definitions and theorems. We learn techniques of proof. In this paper, we describe a particular way to express these techniques and incorporate them into formal theories and into computer systems used to build such theories. We illustrate the methods as they were applied in the -PRL system, essentially using the ML programming language from Edinburgh LCF [23] as the formalised metalanguage. We report our experience with such an approach emphasizing the ideas that go beyond the LCF work, such as transformation tactics and special purpose reasoners. We also show how the validity of tactics can be guaranteed. The introduction places the work in historical context and the conclusion briefly describes plans to carry the methods further. The majority of the paper presents the -PRL approach in detail.Department of Computer Science Technical Report TR84-645. This research supported in part by the National Science Foundation under grant MCS-81-04018.     

A compositional natural semantics and Hoare logic for low-level languages

The advent of proof-carrying code has generated significant interest in reasoning about low-level languages. It is widely believed that low-level languages with jumps must be difficult to reason about because of being inherently non-modular. We argue that this is untrue. We take it seriously that, unlike statements of a high-level language, pieces of low-level code are multiple-entry and multiple-exit. And we define a piece of code as consisting of either a single labelled instruction or a finite union of pieces of code. Thus we obtain a compositional natural semantics and a matching Hoare logic for a basic low-level language with jumps. By their simplicity and intuitiveness, these are comparable to the standard natural semantics and Hoare logic of While. The Hoare logic is sound and complete wrt the semantics and allows for compilation of proofs of the Hoare logic of While.     

Missing Proofs Found

For close to a century, despite the efforts of fine minds that include Hilbert and Ackermann, Tarski and Bernays, ukasiewicz, and Rose and Rosser, various proofs of a number of significant theorems have remained missing – at least not reported in the literature – amply demonstrating the depth of the corresponding problems. The types of such missing proofs are indeed diverse. For one example, a result may be guaranteed provable because of being valid, and yet no proof has been found. For a second example, a theorem may have been proved via metaargument, but the desired axiomatic proof based solely on the use of a given inference rule may have eluded the experts. For a third example, a theorem may have been announced by a master, but no proof was supplied. The finding of missing proofs of the cited types, as well as of other types, is the focus of this article. The means to finding such proofs rests with heavy use of McCune's automated reasoning program OTTER, reliance on a variety of powerful strategies this program offers, and employment of diverse methodologies. Here we present some of our successes and, because it may prove useful for circuit design and program synthesis as well as in the context of mathematics and logic, detail our approach to finding missing proofs. Well-defined and unmet challenges are included.     

Local and global controllability for nonlinear systems

A technique to study local and global controllability properties for a wide class of nonlinear systems is presented. In addition to an extensive study of systems on ² we propose — as an application of our method — a new criterion for global controllability of systems with polynomial drift term, defined on ⁿ. In the case of linear systems, the criterion reduces to the classical Kalman condition.A study of local controllability at the equilibrium point of the drift term of systems defined on ² enables us not only to rederive a local controllability result derived by Hermes [4,5], but also to extend this result when no assumptions are made on the boundedness of the controls.     

Deciding branching time properties for asynchronous programs

Asynchronous programming is a paradigm that supports asynchronous function calls in addition to synchronous function calls. Programs in such a setting can be modeled by automata with counters that keep track of the number of pending asynchronous calls for each function, as well as a call stack for synchronous recursive computation. These programs have the restriction that an asynchronous call is processed only when the call stack is empty. The decidability of the control state reachability problem for such systems was recently established. In this paper, we consider the problems of checking other branching time properties for such systems. Specifically we consider the following problems — termination, which asks if there is an infinite (non-terminating) computation exhibited by the system; control state maintainability, which asks if there is a maximal execution of the system, where all the state visited lie in some “good” set; whether the system can be simulated by a given finite state system; and whether the system can simulate a given finite state system. We present decision algorithms for all these problems.     

Algebraic proofs over noncommutative formulas

We study possible formulations of algebraic propositional proof systems operating with noncommutative formulas. We observe that a simple formulation gives rise to systems at least as strong as Frege, yielding a semantic way to define a Cook-Reckhow (i.e., polynomially verifiable) algebraic analog of Frege proofs, different from that given in Buss et al. (1997) and Grigoriev and Hirsch (2003). We then turn to an apparently weaker system, namely, polynomial calculus (PC) where polynomials are written as ordered formulas (PC over ordered formulas, for short). Given some fixed linear order on variables, an arithmetic formula is ordered if for each of its product gates the left subformula contains only variables that are less-than or equal, according to the linear order, than the variables in the right subformula of the gate. We show that PC over ordered formulas (when the base field is of zero characteristic) is strictly stronger than resolution, polynomial calculus and polynomial calculus with resolution (PCR), and admits polynomial-size refutations for the pigeonhole principle and Tseitin?s formulas. We conclude by proposing an approach for establishing lower bounds on PC over ordered formulas proofs, and related systems, based on properties of lower bounds on noncommutative formulas (Nisan, 1991).The motivation behind this work is developing techniques incorporating rank arguments (similar to those used in arithmetic circuit complexity) for establishing lower bounds on propositional proofs.     

A complete characterization of deterministic regular liveness properties

Many systems can be modeled formally by nondeterministic Büchi-automata. The complexity of model checking then essentially depends on deciding subset conditions on languages that are recognizable by these automata and that represent the system behavior and the desired properties of the system. The involved complementation process may lead to an exponential blow-up in the size of the automata. We investigate a rich subclass of properties, called deterministic regular liveness properties, for which complementation at most doubles the automaton size if the properties are represented by deterministic Büchi-automata. In this paper, we will present a decomposition theorem for this language class that entails a complete characterization of the deterministic regular liveness properties, and extend an existing incomplete result which then, too, characterizes the deterministic regular liveness properties completely.     

Zero-knowledge proofs of retrievability

Proof of retrievability (POR) is a technique for ensuring the integrity of data in outsourced storage services.In this paper,we address the construction of POR protocol on the standard model of interactive proof systems.We propose the first interactive POR scheme to prevent the fraudulence of prover and the leakage of verified data.We also give full proofs of soundness and zero-knowledge properties by constructing a polynomial-time rewindable knowledge extractor under the computational Diffie-Hellman assump...     

Model checking probabilistic social commitments for intelligent agent communication

Interaction among autonomous agents in Multi-Agent Systems (MASs) is a key aspect for agents to coordinate with one another. Social approaches, as opposed to the mental approaches, have recently received a considerable attention in the area of agent communication. They exploit observable social commitments to develop a verifiable formal semantics through which communication protocols can be specified. Developing and implementing algorithmic model checking for social commitments have been recently addressed. However, model checking social commitments in the presence of uncertainty is yet to be investigated.In this paper, we propose a model checking technique for verifying social commitments in uncertain settings. Social commitments are specified in a modal logical language called Probabilistic Computation Tree Logic of Commitments (PCTLC). The modal logic PCTLC extends PCTL, the probabilistic extension of CTL, with modalities for commitments and their fulfillments. The proposed verification method is a reduction-based model checking technique to the model checking of PCTL. The technique is based upon a set of reduction rules that translate PCTLC formulae to PCTL formulae to take benefit of existing model checkers such as PRISM. Proofs that confirm the soundness of the reduction technique are presented. We also present rules that transform our new version of interpreted systems into models of Markov Decision Processes (MDPs) to be suitable for the PRISM tool. We implemented our approach on top of the PRISM model checker and verified some given properties for the Oblivious Transfer Protocol from the cryptography domain. Our simulation demonstrates the effectiveness of our approach in verifying and model checking social commitments in the presence of uncertainty. We believe that the proposed formal verification technique will advance the literature of social commitments in such a way that not only representing social commitments in uncertain settings is doable, but also verifying them in such settings becomes achievable.     

Automating the Search for Elegant Proofs

The research reported in this article was spawned by a colleague's request to find an elegant proof (of a theorem from Boolean algebra) to replace his proof consisting of 816 deduced steps. The request was met by finding a proof consisting of 100 deduced steps. The methodology used to obtain the far shorter proof is presented in detail through a sequence of experiments. Although clearly not an algorithm, the methodology is sufficiently general to enable its use for seeking elegant proofs regardless of the domain of study. In addition to (usually) being more elegant, shorter proofs often provide the needed path to constructing a more efficient circuit, a more effective algorithm, and the like. The methodology relies heavily on the assistance of McCune's automated reasoning program OTTER. Of the aspects of proof elegance, the main focus here is on proof length, with brief attention paid to the type of term present, the number of variables required, and the complexity of deduced steps. The methodology is iterative, relying heavily on the use of three strategies: the resonance strategy, the hot list strategy, and McCune's ratio strategy. These strategies, as well as other features on which the methodology relies, do exhibit tendencies that can be exploited in the search for shorter proofs and for other objectives. To provide some insight regarding the value of the methodology, I discuss its successful application to other problems from Boolean algebra and to problems from lattice theory. Research suggestions and challenges are also offered.