Showing posts with label Computation. Show all posts
Showing posts with label Computation. Show all posts

NP-Completeness of deciding the feasibility of Linear Equations over binary- variables with coefficients and constants that are 0, 1, or -1

2 comments Posted by Dagwood Engelberg

Chermakani, Deepak Ponvel


Abstract
We convert, within polynomial-time and sequential processing, NP-Complete Problemsinto a problem of deciding feasibility of a given system S of linear equations with constants and coefficients of binary-variables that are 0, 1, or -1. S is feasible, if and only if, the NP-Completeproblem has a feasible solution. We show separate polynomial-time conversions to S, from the SUBSET-SUM and 3-SAT problems, both of which are NP-Complete. The number of equations and variables in S is bounded by a polynomial function of the size of the NP-Completeproblem, showing that deciding the feasibility of S is strongly-NP-Complete. Wealsoshow how to apply the approach used for the SUBSET-SUM problemtodecidethe feasibility of Integer Linear Programs, as it involves reducing the coefficient-magnitudes of variables to the logarithm of their initial values, though the number of variables and equations are increased. 


 

Pertaining to: , , ,

Investigations of Quantum Cellular Automata in a Two Dimensional Lattice

1 comments Posted by Dagwood Engelberg

Yiyang Gong

Abstract
Quantum Cellular Automata (QCA) is a feasible method of manipulating a system of qubits carrying quantum information, as the same operations are applied to the entire system. With the proper initial conditions and boundaries for a two dimensional lattice, the state of one qubit can be transported to another qubit on the lattice using QCA. Such a phenomenon represents the possibility of a communication channel between different positions on the lattice. Simulations of the two-dimensional lattice using the stabilizer formalism with proper initial and boundary conditions are demonstrated. Furthermore, various errors on the gates of the system are simulated, and error probabilities on the final results are reported. Finally, encoding schemes using qubit arrays are also investigated.

 

Pertaining to: , , ,

BABEL: A Base for an Experimental Library

0 comments Posted by Dagwood Engelberg

J. Seo, H. Ait-Kaci, R. Nasr

Abstract
This report discusses the implementation of a knowledge base for a library information system. It is done using a typed logic programming language—LOGIN—where type inheritance is built in. The knowledge base is structured in a hierarchical taxonomy of library object classes where each class is represented in a FRAME style knowledge structure and inherits the properties of its parents, and where infrastructural inference rules have been established through typed Horn clauses. Also in this document, some programming techniques aimed at using the power of inheritance as taxonomic inference are discussed.

 

Pertaining to: , ,