The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
In this paper we view P≟NP as the problem which symbolizes the attempt to understand what is and is not feasibly computable. The paper shortly reviews the history of the developments from Gödel's 1956 letter asking for the computational complexity of finding proofs of theorems, through computational complexity, the exploration of complete problems for NP and PSPACE, through the results of structural...
Graph drawing addresses the problem of constructing geometric representations of abstract graphs and networks. It is an emerging area of research that combines flavors of topological graph theory and computational geometry. The automatic generation of drawings of graphs has important applications in key computer technologies such as software engineering, database design, visual interfaces, and computer-aided-design...
Suffix trees are the main data-structure in string matching algorithmes. There are several serial algorithms for suffix tree construction which run in linear time, but the number of operations in the only parallel algorithm available, due to Apostolico, Iliopoulos, Landau, Schieber and Vishkin, is proportional to n log n. The algorithm is based on labeling substrings, similar to a classical serial...
We investigate the relationship beetween the classes MAX-NP and GLO by studying the Maximum Generalized Satisfiability problem, which is in the former class. We present a (2−B)-approximate greedy heuristic for this problem and show that no local search c-approximate algorithm exists, based on an h-bounded neighborhood and on the number of satisfied clauses as objective function. This implies that,...
We consider the problem of identifying the behavior of an unknown automaton with multiplicity in the field Q of rational numbers (Q-automaton) from multiplicity and equivalence queries. We provide an algorithm which is polynomial in the size of the Q-automaton and of the maximum length of the given counterexamples. As a consequence, we have that Q-automata are PAC-learnable in polynomial time when...
In this paper We study some measures of complexity for Boolean functions based on Abstract Harmonic Analysis. More precisely, we extend the notion of average sensitivity of Boolean functions and introduce the generalized sensitivity (or k-sensitivity) which accounts for the changes in the function value when k input bits are flipped. We find the connection between k-sensitivity and Fourier coefficients...
Studying the computational complexity of the Configuration Reachabilty Problem (CREP) is a good way to investigate properties of a given discrete deterministic dynamical system like a Toroidal Cellular Automaton (TCA). We study CREP for two natural weakly predictable classes of TCA: the booleandisjunctive class and the additive one. For the first class, we reduce CREP to a path problem on a strongly...
We introduce pruning decomposition, a new method of graph decom position which is very useful in developing a parallel algorithm for graph problems on EREW P-RAM. We present parallel algorithms that achieve the decomposition and an parallel algorithm for finding biconnected components of graphs based on the pruning decomposition. The complexity for both algorithms on EREW P-RAM is dominated by the...
We give the first electronic cash system whose transactions require no interaction between the parties. Its security is based on the computational intractability of factoring Blum integers. We also give a non-interactive perfect zero-knowledge proof system of membership to the language of Blum integers. We use this proof system in our electronic cash system as a tool for proving the correctness...
We propose a scheme for constructing expander based networks, by starting with a skeleton (directed and weighted) graph, and fleshing out its edges into expanders. Particular cases which can be built this way are: the multibutterfly, the multi-Beneš, a certain fat-tree and a superconcentrator. The problem of on-line deterministic routing through any expander based network is shown to be solvable...
Many AI tasks can be formulated as a Constraint Satisfaction Problem (CSP), i.e. the problem of finding an assignment of values for a set of variables subject to a given collection of constraints. In this framework each constraint is defined over a set of variables and specifies the set of allowed combinations of values as a collection of tuples. In some cases the knowledge of the problem defined...
We consider the problem of maintaining a binary search tree that minimizes the average access cost with respect to randomly generated requests. We analyze scenarios, in which the accesses are generated according to a vector of probabilities, which is fixed but unknown. In this paper we devise policies for modifying the tree structure dynamically, using rotations of accessed elements towards...
A set of anonymous processors is interconnected forming a complete synchronous network with sense of direction. Weak unison is the problem where all processors want to enter the same state (in our case “wakeup” state) in the absence of a global start-up signal. As measure of complexity of the protocols considered we use the “bits” times “lag” measure, i.e. the total number of (wakeup) messages transmitted...
This paper is concerned with data structures for representing an arbitrary number of sets of keys such that we can update the sets dynamically, query the membership of a set, and test whether two sets are equal. Such data structures have been studied intensively by a number of researchers [2, 6, 4, 5, 7]. Prior to our work, the best scheme supports set equalitytesting in constant time and the operations...
In this paper we introduce the notion of rewriting systems for sets, and consider the complexity of the reachability problems for these systems, showing that this problem is PSPACE-complete in the general case and is P-complete for particular rewriting systems. As a consequence, we show that the emptiness and finiteness problems for E0L systems are PSPACE-complete, solving in this way an open problem...
Self-reducible sets have a rich internal structure. The information contained in these sets is encoded in some redundant way. Therefore a lot of the information of the set is easily accessible. In this paper it is investigated how this self-reducibility structure of a set can be used to access easily all information contained in the set, if its information content is small. It is shown that P can...
We show lower bounds for the problems of merging two sorted lists of equal length and sorting by repeatedly merging pairs of sorted sequences on the hypercube. These lower bounds hold on the average for any ordering of the processors of the hypercube.
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.