共查询到20条相似文献,搜索用时 15 毫秒
1.
Self-assembly is a process in which small objects autonomously associate with each other to form larger complexes. It is ubiquitous in biological constructions at the cellular and molecular scale and has also been identified by nanoscientists as a fundamental method for building nano-scale structures. Recent years have seen convergent interest and efforts in studying self-assembly from mathematicians, computer scientists, physicists, chemists, and biologists. However most complexity theoretical studies of self-assembly utilize mathematical models with two limitations: (1) only attraction, while no repulsion, is studied; (2) only assembled structures of two dimensional square grids are studied. In this paper, we study the complexity of the assemblies resulting from the cooperative effect of repulsion and attraction in a more general setting of graphs. This allows for the study of a more general class of self-assembled structures than the previous tiling model. We define two novel assembly models, namely the accretive graph assembly model and the self-destructible graph assembly model, and identify a fundamental problem in them: the sequential construction of a given graph. We refer to it as the Accretive Graph Assembly Problem (AGAP) and the Self-Destructible Graph Assembly Problem (DGAP), in the respective models. Our main results are: (i) AGAP is NP-complete even if the maximum degree of the graph is restricted to 4 or the graph is restricted to be planar with maximum degree 5; (ii) counting the number of sequential assembly orderings that result in a target graph (#AGAP) is #P-complete; and (iii) DGAP is PSPACE-complete even if the maximum degree of the graph is restricted to 6 (this is the first PSPACE-complete result in self-assembly). We also extend the accretive graph assembly model to a stochastic model, and prove that determining the probability of a given assembly in this model is #P-complete. 相似文献
2.
Let be a fixed collection of digraphs. Given a digraph H, a -packing of H is a collection of vertex disjoint subgraphs of H, each isomorphic to a member of . For undirected graphs, Loebl and Poljak have completely characterized the complexity of deciding the existence of a perfect -packing, in the case that consists of two graphs one of which is a single edge on two vertices. We characterize -packing where consists of two digraphs one of which is a single arc on two vertices. 相似文献
3.
4.
Parameterized power domination complexity 总被引:1,自引:0,他引:1
Joachim Kneis 《Information Processing Letters》2006,98(4):145-149
The optimization problem of measuring all nodes in an electrical network by placing as few measurement units (PMUs) as possible is known as Power Dominating Set. Nodes can be measured indirectly according to Kirchhoff's law. We show that this problem can be solved in linear time for graphs of bounded treewidth and establish bounds on its parameterized complexity if the number of PMUs is the parameter. 相似文献
5.
Michael Wooldridge 《Artificial Intelligence》2004,158(1):27-73
We study coalitional games in which agents are each assumed to have a goal to be achieved, and where the characteristic property of a coalition is a set of choices, with each choice denoting a set of goals that would be achieved if the choice was made. Such qualitative coalitional games (qcgs) are a natural tool for modelling goal-oriented multiagent systems. After introducing and formally defining qcgs, we systematically formulate fourteen natural decision problems associated with them, and determine the computational complexity of these problems. For example, we formulate a notion of coalitional stability inspired by that of the core from conventional coalitional games, and prove that the problem of showing that the core of a qcg is non-empty is Dp1-complete. (As an aside, we present what we believe is the first “natural” problem that is proven to be complete for Dp2.) We conclude by discussing the relationship of our work to other research on coalitional reasoning in multiagent systems, and present some avenues for future research. 相似文献
6.
7.
I. Krasikov 《Information Processing Letters》2004,92(3):117-119
We study the problem of finding the next-to-shortest paths in a graph. A next-to-shortest (u,v)-path is a shortest (u,v)-path amongst (u,v)-paths with length strictly greater than the length of the shortest (u,v)-path. In contrast to the situation in directed graphs, where the problem has been shown to be NP-hard, providing edges of length zero are allowed, we prove the somewhat surprising result that there is a polynomial time algorithm for the undirected version of the problem. 相似文献
8.
9.
10.
11.
On the computational complexity of coalitional resource games 总被引:1,自引:0,他引:1
Michael Wooldridge 《Artificial Intelligence》2006,170(10):835-871
We study Coalitional Resource Games (crgs), a variation of Qualitative Coalitional Games (qcgs) in which each agent is endowed with a set of resources, and the ability of a coalition to bring about a set of goals depends on whether they are collectively endowed with the necessary resources. We investigate and classify the computational complexity of a number of natural decision problems for crgs, over and above those previously investigated for qcgs in general. For example, we show that the complexity of determining whether conflict is inevitable between two coalitions with respect to some stated resource bound (i.e., a limit value for every resource) is co-np-complete. We then investigate the relationship between crgs and qcgs, and in particular the extent to which it is possible to translate between the two models. We first characterise the complexity of determining equivalence between crgs and qcgs. We then show that it is always possible to translate any given crg into a succinct equivalent qcg, and that it is not always possible to translate a qcg into an equivalent crg; we establish some necessary and some sufficient conditions for a translation from qcgs to crgs to be possible, and show that even where an equivalent crg exists, it may have size exponential in the number of goals and agents of its source qcg. 相似文献
12.
A vertex-colored graph is rainbow vertex-connected if any two vertices are connected by a path whose internal vertices have distinct colors, which was introduced by Krivelevich and Yuster. The rainbow vertex-connection of a connected graph G, denoted by rvc(G), is the smallest number of colors that are needed in order to make G rainbow vertex-connected. In this paper, we study the complexity of determining the rainbow vertex-connection of a graph and prove that computing rvc(G) is NP-Hard. Moreover, we show that it is already NP-Complete to decide whether rvc(G)=2. We also prove that the following problem is NP-Complete: given a vertex-colored graph G, check whether the given coloring makes G rainbow vertex-connected. 相似文献
13.
Colouring a graph with its chromatic number of colours is known to be NP-hard. Identifying an algorithm in which decisions are made locally with no information about the graph's global structure is particularly challenging. In this article we analyse the complexity of a decentralised colouring algorithm that has recently been proposed for channel selection in wireless computer networks. 相似文献
14.
Tom Rackham 《Information Processing Letters》2010,110(17):735-739
Let G be a graph, x,y∈V(G), and ?:V(G)→[k] a k-colouring of G such that ?(x)=?(y). If then the following question is NP-complete: Does there exist a k-colouring ?′ of G such that ?′(x)≠?′(y)? Conversely, if then the problem is polynomial time. 相似文献
15.
Stasys Jukna 《Information Processing Letters》2005,96(6):202-206
We consider the analog of the P versus NP∩co-NP question for the classical two-party communication protocols where polynomial time is replaced by poly-logarithmic communication: if both a boolean function f and its negation ¬f have small (poly-logarithmic in the number of variables) nondeterministic communication complexity, what is then its deterministic and/or probabilistic communication complexity? In the fixed (worst) partition model of communication this question was answered by Aho, Ullman and Yannakakis in 1983: here P=NP∩co-NP.We show that in the best partition model of communication the situation is entirely different: here P is a proper subset even of RP∩co-RP. This, in particular, resolves an open question raised by Papadimitriou and Sipser in 1982. 相似文献
16.
Serge Gaspers 《Information Processing Letters》2009,109(10):463-467
We prove a relationship between the Cleaning problem and the Balanced Vertex-Ordering problem, namely that the minimum total imbalance of a graph equals twice the brush number of a graph. This equality has consequences for both problems. On one hand, it allows us to prove the NP-completeness of the Cleaning problem, which was conjectured by Messinger et al. [M.-E. Messinger, R.J. Nowakowski, P. Pra?at, Cleaning a network with brushes, Theoret. Comput. Sci. 399 (2008) 191-205]. On the other hand, it also enables us to design a faster algorithm for the Balanced Vertex-Ordering problem [J. Kára, K. Kratochvíl, D. Wood, On the complexity of the balanced vertex ordering problem, Discrete Math. Theor. Comput. Sci. 9 (1) (2007) 193-202]. 相似文献
17.
Fabian SchwarzerAchim Schweikard 《Information Processing Letters》2002,83(4):187-194
The problem of deciding whether 2- or 3-dimensional objects can be separated by a sequence of arbitrary translational motions is known to have exponential lower bounds. However, under certain restrictions on the type of motions, polynomial time bounds have been shown. An example is finding a subset of the parts that is removable by a single translation. In this case, the main restriction is that all selected parts are required to be removed in the same direction and with the same velocity. It was an open question whether the polynomial time bound can be achieved if more than a single velocity is allowed for the moving parts. In this paper, we answer this question by proving that such ‘multi-handed’ separability problems are NP-hard. 相似文献
18.
We show that computing the lexicographically first four-coloring for planar graphs is -hard. This result optimally improves upon a result of Khuller and Vazirani who prove this problem NP-hard, and conclude that it is not self-reducible in the sense of Schnorr, assuming P≠NP. We discuss this application to non-self-reducibility and provide a general related result. We also discuss when raising a problem's NP-hardness lower bound to -hardness can be valuable. 相似文献
19.
Computational complexity analysis of set membership identification of Hammerstein and Wiener systems
Mario Sznaier Author Vitae 《Automatica》2009,45(3):701-705
This paper analyzes the computational complexity of set membership identification of Hammerstein and Wiener systems. Its main results show that, even in cases where a portion of the plant is known, the problems are generically NP-hard both in the number of experimental data points and in the number of inputs (Wiener) or outputs (Hammerstein) of the nonlinearity. These results provide new insight into the reasons underlying the high computational complexity of several recently proposed algorithms and point out the need for developing computationally tractable relaxations. 相似文献
20.
P. Liberatore 《人工智能实验与理论杂志》2013,25(3):283-295
This paper analyses the computational complexity of problems related to case-based planning: planning when a plan for a similar instance is known, and planning from a library of plans. It is proven that planning from a single case has the same complexity than generative planning (i.e. planning ‘from scratch’); using an extended definition of cases, complexity is reduced if the domain stored in the case is similar to the one to search plans for. Planning from a library of cases is shown to have the same complexity. In both cases, the complexity of planning remains, in the worst case, PSPACE-complete. 相似文献