BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
The problem of deciding if a Traveling Salesman Problem (TSP) tour is minimal was proved to be coNP-complete by Papadimitriou and Steiglitz. We give an alternative proof based on a polynomial time reduction from 3SAT. Like the original proof, our reduction also shows that given a graph G and an Hamiltonian path of G, it is NP-complete to check if G contains an Hamiltonian cycle (Restricted Hamiltonian Cycle problem).
We prove that the problem of reconstructing a permutation π1,…,πn of the integers [1…n] given the absolute differences ∣πi+1−πi∣, i=1,…,n−1 is NP-complete. As an intermediate step we first prove the NP-completeness of the decision version of a new puzzle game that we call Crazy Frog Puzzle. The permutation reconstruction from differences is one of the simplest combinatorial problems that have been proved to be computationally intractable.
A two-way deterministic finite state automaton with one counter (2D1CA) is a fundamental computational model that has been examined in many different aspects since sixties, but we know little about its power in the case of unary languages. Up to our knowledge, the only known unary nonregular languages recognized by 2D1CAs are those formed by strings having exponential length, where the exponents form some trivial unary regular language. In this paper, we present some non-trivial subsets of these languages. By using the input head as a second counter, we present simulations of two-way deterministic finite automata with linearly bounded counters and linear--space Turing machines. We also show how a fixed-size quantum register can help to simplify some of these languages. Finally, we compare unary 2D1CAs with two--counter machines and provide some insights about the limits of their computational power.
Data replication technologies enable efficient and highly-available data access, thus gaining more and more interests in both the academia and the industry. However, data replication introduces the problem of data consistency. Modern commercial data replication systems often provide weak consistency for high availability under certain failure scenarios. An important weak consistency is Pipelined-RAM (PRAM) consistency. It allows different processes to hold different views of data. To determine whether a data replication system indeed provides PRAM consistency, we study the problem of Verifying PRAM Consistency over read/write traces (or VPC, for short). We first identify four variants of VPC according to a) whether there are Multiple shared variables (or one Single variable), and b) whether write operations can assign Duplicate values (or only Unique values) for each shared variable; the four variants are labeled VPC-SU, VPC-MU, VPC-SD, and VPC-MD. Second, we present a simple VPC-MU algorithm, called RW-CLOSURE. It constructs an operation graph G by iteratively adding edges according to three rules. Its time complexity is O(n5), where n is the number of operations in the trace. Third, we present an improved VPC-MU algorithm, called READ-CENTRIC, with time complexity O(n4). Basically it attempts to construct the operation graph G in an incremental and efficient way. Its correctness is based on that of RW-CLOSURE. Finally, we prove that VPC-SD (so is VPC-MD) is NP-complete by reducing the strongly NP-complete problem 3-PARTITION to it.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.