Search

In this article, we introduce a Prover-Verifier model for analysing the computational complexity of a class of constraint satisfaction problems (CSPs) termed boolean binary constraint satisfaction problems (BBCSPs). BBCSPs represent an extremely general class of CSPs and find applications in a wide variety of domains including constraint programming, puzzle solving and program testing. The constraints in a BBCSP permit the combination of multiple theories as opposed to traditional constraint systems in which all constraints belong to the same theory. We establish that each instance of a BBCSP admits a coin-flipping Turing machine that halts in time polynomial in the size of the input. Furthermore, the algorithm is oblivious in that it never sees more than one constraint at a time. The prover, P, in the Prover-Verifier model is endowed with very limited powers. In particular, it has no memory and it can only pose restricted queries to the verifier. The verifier, on the other hand, is both omniscient in that it is cognisant of all the problem details and insincere in that it does not have to decide a priori on the intended proof. However, the verifier must stay consistent in its responses, i.e. it cannot rule out a certain possibility in one response to a query from the prover and then rule in the same possibility in response to a subsequent query. We note that the combination of the resources required by the prover and the type of certificate demanded of the verifier, determine the resources required by an algorithm. Inasmuch as our provers will be memoryless and our verifiers will be asked for extremely simple certificates, our work establishes the existence of a simple, randomised algorithm for BBCSPs. Our model itself serves as a basis for the design of zero-knowledge machine learning algorithms in that the prover ends up learning the proof desired by the verifier. Likewise, our work finds applications in the domain of certifying algorithm design, wherein the goal is to provide a proof of correctness of the algorithm on the input instance by providing an easily checkable certificate. [ABSTRACT FROM AUTHOR]

We contrast the performance of three algorithms for the problem of deciding whether a Partially Clairvoyant real-time system with relative timing constraints, as specified in the E-T-C scheduling framework, has a feasible schedule. In the E-T-C scheduling model, real-time scheduling problems are specified through a specialized class of constraint logic programs (CLPs) called Quantified Linear Programs (QLPs) [Subramani, K., 2003, An analysis of quantified linear programs. In: C.S. Calude (Ed.) Proceedings of the 4th International Conference on Discrete Mathematics and Theoretical Computer Science (DMTCS), volume 2731 of Lecture Notes in Computer Science, July (Springer-Verlag), pp. 265- 277]; thus algorithms for determining the schedulability of instances are procedures to determine the satisfiability of CLPs. Two of these algorithms, viz., the primal algorithm and the dual algorithm have already been discussed in the literature, while a third algorithm called the randomized dual algorithm has been recently proposed [Subramani, K. and Desovski, D. 2005, A new verification procedure for partially Clairvoyant scheduling. Proceedings of the 3rd International Conference on Formal Modelling and Analysis of Timed Systems (FORMATS), October; Subramani, K. and Desovski, D., 2005, Out of order quantifier elimination for standard quantified linear programs, Journal of Symbolic Computation, 40, 1383-1396]. Our experiments demonstrate that the dual-based algorithms (i.e. the dual and the randomized dual) are more effective from an implementational perspective; this is surprising since all three algorithms have the same worst case asymptotic complexity. [ABSTRACT FROM AUTHOR]

Abstract: This paper is concerned with the problem of checking whether a network with positive and negative costs on its arcs contains a negative cost cycle. The Negative Cost Cycle Detection (NCCD) problem is one of the more fundamental problems in network design and finds applications in a number of domains ranging from Network Optimization and Operations Research to Constraint Programming and System Verification. As per the literature, approaches to this problem have been either Relaxation-based or Contraction-based. We introduce a fundamentally new approach for negative cost cycle detection; our approach, which we term as the Stressing Algorithm, is based on exploiting the connections between the NCCD problem and the problem of checking whether a system of difference constraints is feasible. The Stressing Algorithm is an incremental, comparison-based procedure which is as efficient as the fastest known comparison-based algorithm for this problem. In particular, on a network with n vertices and m edges, the Stressing Algorithm takes time to detect the presence of a negative cost cycle or to report that none exists. A very important feature of the Stressing Algorithm is that it uses zero extra space; this is in marked contrast to all known algorithms that require extra space. It is well known that the NCCD problem is closely related to the Single Source Shortest Paths (SSSP) problem, i.e., the problem of determining the shortest path distances of all the vertices in a network, from a specified source; indeed most algorithms in the literature for the NCCD problem are modifications of approaches to the SSSP problem. At this juncture, it is not clear whether the Stressing Algorithm could be extended to solve the SSSP problem, even if extra space is available. [Copyright &y& Elsevier]

The article presents a study on chain programming over difference constraints. Chain programming is a restricted form of linear programming, and a chain program is characterized by a total ordering on the program variables. The study has shown that for difference constraint systems, the total ordering of the program variables results in an elegant divide and conquer algorithm for the problem of feasibility testing.

Abstract: In this paper, we present an out of order quantifier elimination algorithm for a class of Quantified Linear Programs (QLPs) called Standard Quantified Linear Programs (SQLPs). QLPs in general and SQLPs in particular are extremely useful constraint logic programming structures that find wide applicability in the modeling of real-time schedulability specifications; see Subramani [Subramani, K., 2005a. A comprehensive framework for specifying clairvoyance, constraints and periodicity in real-time scheduling. The Computer Journal 48 (3), 259–272]. Consequently any algorithmic advance in their solution has a strong practical impact. Prior to this work, the only known approaches to the solution of QLPs involved sequential variable elimination; see Subramani [Subramani, K., 2003b. An analysis of quantified linear programs. In: Calude, C.S. et al. (Eds.), Proceedings of the 4th International Conference on Discrete Mathematics and Theoretical Computer Science. DMTCS. In: Lecture Notes in Computer Science, vol. 2731. Springer-Verlag, pp. 265–277]. In the sequential approach, the innermost quantified variable is eliminated first, followed by the variable which then becomes the innermost quantified variable and so on, until we are left with a single variable from which the satisfiability of the original formula is easily deduced. This approach is applicable in both discrete and continuous domains; however, it is to be noted that the logic demanding the sequential approach requires that the variables are discrete-valued. To the best of our knowledge, the necessity for sequential elimination over continuous-valued variables has not been investigated in the literature. The techniques used in the development of our elimination algorithm may find applications in domains such as classical logic and finite model theory. The final aspect of our research concerns the structure-preserving nature of the algorithm that we introduce here; in general, it is not known whether discrete domains admit such elimination procedures. [Copyright &y& Elsevier]

In this paper we introduce a problem called Quantified Integer Programming, which generalizes the Quantified Satisfiability problem (QSAT). In a Quantified Integer Program (QIP) the program variables can assume arbitrary integral values, as opposed to the boolean values that are assumed by the variables of an instance of QSAT. QIPs naturally represent two-person integer matrix games. The Quantified Integer Programming problem is PSPACE-hard in general, since the QSAT problem is PSPACE-complete. Quantified Integer Programming can be thought of as a restriction of Presburger Arithmetic, in that we allow only conjunctions of linear inequalities. We focus on analyzing various special cases of the general problem, with a view to discovering subclasses that are tractable. Subclasses of the general QIP problem are obtained by restricting either the constraint matrix or quantifier specification or both. We show that if the constraint matrix is totally unimodular, the problem of deciding a QIP can be solved in polynomial time. We also establish the computational complexities of Oblivious strategy games and Clairvoyant strategy games. [ABSTRACT FROM AUTHOR]