The computational complexity of the meshless local Petrov-Galerkin method (MLPG) has been analyzed and compared with the finite difference (FDM) and finite element methods (FEM) from the user point of view. Theoretica...
详细信息
The computational complexity of the meshless local Petrov-Galerkin method (MLPG) has been analyzed and compared with the finite difference (FDM) and finite element methods (FEM) from the user point of view. Theoretically, MLPG is the most complex of the three methods. Experimental results show that MLPG, with appropriately selected integration order and dimensions of support and quadrature domains, achieves similar accuracy to that of FEM. The measurements of parallel complexity and speed-up indicate that parallel MLPG scales well on larger systems. The normalized computational complexity makes FEM the best choice. MLPG remains competitive if human assistance is needed for meshing. (C) 2008 Elsevier Ltd. All rights reserved.
We study the computational complexity of auditing finite attributes in databases allowing statistical queries. Given a database that supports statistical queries, the auditing problem is to check whether an attribute ...
详细信息
We study the computational complexity of auditing finite attributes in databases allowing statistical queries. Given a database that supports statistical queries, the auditing problem is to check whether an attribute can be completely determined or not from a given set of statistical information. Some restricted cases of this problem have been investigated earlier, e.g. the complexity of statistical sum queries is known by the work of Kleinberg et al. (J. Comput. System Sci. 66 (2003) 244-253). We characterize all classes of statistical queries such that the auditing problem is polynomial-time solvable. We also prove that the problem is coNP-complete in all other cases under a plausible conjecture on the complexity of constraint satisfaction problems (CSP). The characterization is based on the complexity of certain CSP problems;the exact complexity for such problems is known in many cases. This result is obtained by exploiting connections between auditing and constraint satisfaction, and using certain algebraic techniques. We also study a generalization of the auditing problem where one asks if a set of statistical information imply that an attribute is restricted to K or less different values. We characterize all classes of polynomial-time solvable problems in this case, too. (c) 2008 Elsevier Inc. All rights reserved.
The sensor location flow observability problem is studied from the computational complexity point of view. Although the general problem is shown to be NP-complete, by studying the special cases of input matrix structu...
详细信息
The sensor location flow observability problem is studied from the computational complexity point of view. Although the general problem is shown to be NP-complete, by studying the special cases of input matrix structures and data where the corresponding problems are polynomially solvable, the boundary between NP-complete and polynomial solvable problems is delineated.
Sofic shifts are symbolic dynamical systems defined by the set of bi-infinite sequences on an edge-labeled directed graph, called a presentation. We study the computational complexity of an array of natural decision p...
详细信息
Sofic shifts are symbolic dynamical systems defined by the set of bi-infinite sequences on an edge-labeled directed graph, called a presentation. We study the computational complexity of an array of natural decision problems about presentations of sofic shifts, such as whether a given graph presents a shift of finite type, or an irreducible shift;whether one graph presents a subshift of another;and whether a given presentation is minimal, or has a synchronizing word. Leveraging connections to automata theory, we first observe that these problems are all decidable in polynomial time when the given presentation is irreducible (strongly connected), via algorithms both known and novel to this work. For the general (reducible) case, however, we show they are all PSPACE-complete. All but one of these problems (subshift) remain polynomial-time solvable when restricting to synchronizing deterministic presentations. We also study the size of synchronizing words and synchronizing deterministic presentations. (c) 2022 Elsevier B.V. All rights reserved.
We show that the popular pencil puzzle NURIKABE is intractable from the computational complexity point of view, that is, it is NP-complete, even when the involved numbers are 1 and 2 only. To this end, we show how to ...
详细信息
We show that the popular pencil puzzle NURIKABE is intractable from the computational complexity point of view, that is, it is NP-complete, even when the involved numbers are 1 and 2 only. To this end, we show how to simulate Boolean gates by the puzzle under consideration. Moreover, we also study some NURIKABE variants, which remain NP-complete, too.
A covering projection from a graph G onto a graph H is a mapping of the vertices of G onto the vertices of H such that, for every vertex v of G, the neighborhood of v is mapped bijectively onto the neighborhood of its...
详细信息
A covering projection from a graph G onto a graph H is a mapping of the vertices of G onto the vertices of H such that, for every vertex v of G, the neighborhood of v is mapped bijectively onto the neighborhood of its image. Moreover, if G and H are multigraphs, then this local bijection has to preserve multiplicities of the neighbors as well. The notion of covering projection stems from topology, but has found applications in areas such as the theory of local computation and construction of highly symmetric graphs. It provides a restrictive variant of the constraint satisfaction problem with additional symmetry constraints on the behavior of the homomorphisms of the structures involved. We investigate the computational complexity of the problem of deciding the existence of a covering projection from an input graph G to a fixed target graph H. Among other partial results this problem has been shown NP-hard for simple regular graphs H of valency greater than 2, and a full characterization of computational complexity has been shown for target multigraphs with 2 vertices. We extend the previously known results to the ternary case, i.e., we give a full characterization of the computational complexity in the case of multigraphs with 3 vertices. We show that even in this case a P/NP-completeness dichotomy holds. (C) 2015 Elsevier B.V. All rights reserved.
Branched junction molecule assembly of DNA nanostructures, pioneered by Seeman's laboratory in the 1980s, has become increasingly sophisticated, as have the assembly targets. A critical design step is finding mini...
详细信息
Branched junction molecule assembly of DNA nanostructures, pioneered by Seeman's laboratory in the 1980s, has become increasingly sophisticated, as have the assembly targets. A critical design step is finding minimal sets of branched junction molecules that will self-assemble into target structures without unwanted substructures forming. We use graph theory, which is a natural design tool for self-assembling DNA complexes, to address this problem. After determining that finding optimal design strategies for this method is generally NP-complete, we provide pragmatic solutions in the form of programs for special settings and provably optimal solutions for natural assembly targets such as platonic solids, regular lattices, and nanotubes. These examples also illustrate the range of design challenges.
Hilbert's Irreducibility Theorem is applied to find the upper bounds of the time complexities of various decision problems in arithmetical sentences and the following results are proved: 1. The decision problem of...
详细信息
Hilbert's Irreducibility Theorem is applied to find the upper bounds of the time complexities of various decision problems in arithmetical sentences and the following results are proved: 1. The decision problem of for all there exists sentences over an algebraic number field is in P. 2. The decision problem of for all there exists sentences over the collection of all fields with characteristic 0 is in P. 3. The decision problem of for all there exists sentences over a function field with characteristic p is polynomial time reducible to the factorization of polynomials over Z(p). 4. The decision problem of for all there exists sentences over the collection of all-fields with characteristic p is polynomial time reducible to the factorization of polynomials over Zp. 5. The decision problem of for all there exists sentences over the collection of all fields is polynomial time reducible to the factorization of integers over Z and the factorization of polynomials over finite fields. (c) 2008 Published by Elsevier Inc.
In situations when a group of people has to make a decision based on the set of individual preferences, they use a certain aggregation method, in particular, voting. One of the main problems for any non-dictatorial so...
详细信息
In situations when a group of people has to make a decision based on the set of individual preferences, they use a certain aggregation method, in particular, voting. One of the main problems for any non-dictatorial social choice rule is the possibility for the voters to achieve a more preferable outcome of the voting by misrepresenting their preferences. Such actions on behalf of the voters are called manipulation, or strategic voting. One approach used to compare social choice rules in terms of how hard they are to manipulate is to find the complexity classes of manipulation problems for a given aggregation method. In this work, we present a survey of the studies of complexity classes of manipulation problems under various model assumptions and constraints.
Some diffusive and recurrence properties of Lorentz Lattice Gas Cellular Automata (LLGCA) have been expensively studied in terms of the densities of some of the left/right static/flipping mirrors/rotators. In this pap...
详细信息
Some diffusive and recurrence properties of Lorentz Lattice Gas Cellular Automata (LLGCA) have been expensively studied in terms of the densities of some of the left/right static/flipping mirrors/rotators. In this paper, for any combination S of these well known scatters, we study the computational complexity of the following problem which we call PERIODICITY on the S-model: given a finite configuration that distributes only those scatters in S, whether a particle visits the starting position periodically or not. Previously, the flipping mirror model and the occupied flipping rotator model have been shown unbounded, i.e. the process is always diffusive [17]. On the other hand, PERIODICITY is shown PSPACEcomplete in the unoccupied flipping rotator model [21]. In this paper, we show that PERIODICITY is PSPACE-compete in any S-model that is neither occupied, unbounded, nor static. Particularly, we prove that PERIODICITY in any unoccupied and bounded model containing flipping mirror is PSPACEcomplete.
暂无评论