In this paper, we solve a widely publicized open problem posed by Peter Winkler in 1988. The problem is to decide whether or not it is possible to partition the vertices of a graph into four distinct nonempty sets A, ...
详细信息
In this paper, we solve a widely publicized open problem posed by Peter Winkler in 1988. The problem is to decide whether or not it is possible to partition the vertices of a graph into four distinct nonempty sets A, B, C, and D, such that there is no edge between the sets A and C, and between the sets B and D, and that there is at least one edge between any other pair of distinct sets. Winkler asked whether this problem is NP-complete. We show in this paper that it is NP-complete. We study the problem as the compaction problem for a reflexive 4-cycle. We also show in this paper that the compaction problem for a reflexive k-cycle is NP-complete for all k greater than or equal to 4.
In this paper we prove that the general avalanche problem AP is in NC for all decreasing sandpile models in one dimension. It extends the developments of [5], and requires a careful attention on the general rule set c...
详细信息
In this paper we prove that the general avalanche problem AP is in NC for all decreasing sandpile models in one dimension. It extends the developments of [5], and requires a careful attention on the general rule set considered, stressing the importance of the decreasing property. This work continues the study of dimension sensitive problems since in higher dimensions the problem is P-complete (for monotone sandpiles).
Recently there has been a flurry of research in the area of production planning for multi-echelon production-distribution systems with deterministic non-stationary demands and no capacity constraints. A variety of alg...
详细信息
Recently there has been a flurry of research in the area of production planning for multi-echelon production-distribution systems with deterministic non-stationary demands and no capacity constraints. A variety of algorithms have been proposed to optimally solve these problems, with varying success. This paper investigates the issue of computational complexity of the problem for all commonly studied product structures, i.e. the single item, the serial system, the assembly system, the one-warehouse- N -retailer system, the distribution system, the joint replenishment system, and the general production-distribution system. Polynomial time algorithms are available for the single-item, serial and assembly systems. We prove that the remaining problems are NP-complete.
The main contribution of this paper is the development and application of cryptographic techniques to the design of strategic communication mechanisms. One of the main assumptions in cryptography is the limitation of ...
详细信息
The main contribution of this paper is the development and application of cryptographic techniques to the design of strategic communication mechanisms. One of the main assumptions in cryptography is the limitation of the computational power available to agents. We introduce the concept of limited computational complexity, and by borrowing results from cryptography, we construct a communication protocol to establish that every correlated equilibrium of a two-person game with rational payoffs can be achieved by means of computationally restricted unmediated communication. This result provides an example in game theory where limitations of computational abilities of players are helpful in solving implementation problems. More specifically, it is possible to construct mechanisms with the property that profitable deviations are too complicated to compute.
In this paper, it is shown that the problem of deciding whether or not a geometric diagram in Euclidean Geometry is satisfiable is NP-hard and in PSPACE, and in fact has the same complexity as the satisfaction problem...
详细信息
In this paper, it is shown that the problem of deciding whether or not a geometric diagram in Euclidean Geometry is satisfiable is NP-hard and in PSPACE, and in fact has the same complexity as the satisfaction problem for a fragment of the existential theory of the real numbers. The related problem of finding all of the possible (satisfiable) diagrams that can result when a segment of a diagram is extended is also shown to be NP-hard. (c) 2005 Elsevier Inc. All rights reserved.
The problem of DISTANCE EDGE LABELING is a variant of DISTANCE VERTEX LABELING (also known as L-2,L-1 labeling) that has been studied for more than twenty years and has many applications, such as frequency assignment....
详细信息
The problem of DISTANCE EDGE LABELING is a variant of DISTANCE VERTEX LABELING (also known as L-2,L-1 labeling) that has been studied for more than twenty years and has many applications, such as frequency assignment. The DISTANCE EDGE LABELING problem asks whether the edges of a given graph can be labeled such that the labels of adjacent edges differ by at least two and the labels of edges at distance two differ by at least one. Labels are chosen from the set {0, 1,, lambda} for A fixed. We present a full classification of its computational complexity-a dichotomy between the polynomial-time solvable cases and the remaining cases which are NP-complete. We characterize graphs with lambda <= 4 which leads to a polynomial-time algorithm recognizing the class and we show NP-completeness for lambda >= 5 by several reductions from MONOTONE NOT ALL EQUAL 3-SAT. Moreover, there is an absolute constant c > 0 such that there is no 2(cn)-time algorithm deciding the DISTANCE EDGE LABELING problem unless the exponential time hypothesis fails. (C) 2017 Elsevier B.V. All rights reserved.
Diffusion-Limited Aggregation (DLA) is a cluster-growth model that consists in a set of particles that are sequentially aggregated over a two-dimensional grid. In this paper, we introduce a biased version of the DLA m...
详细信息
Diffusion-Limited Aggregation (DLA) is a cluster-growth model that consists in a set of particles that are sequentially aggregated over a two-dimensional grid. In this paper, we introduce a biased version of the DLA model, in which particles are limited to move in a subset of possible directions. We denote by k-DLA the model where the particles move only in k possible directions. We study the biased DLA model from the perspective of computational complexity, defining two decision problems The first problem is Prediction, whose input is a site of the grid c and a sequence S of walks, representing the trajectories of a set of particles. The question is whether a particle stops at site c when sequence S is realized. The second problem is Realization, where the input is a set of positions of the grid, P. The question is whether there exists a sequence S that realizes P, i.e. all particles of S exactly occupy the positions in P. Our aim is to classify the Prediciton and Realization problems for the different versions of DLA. We first show that Prediction is P-Complete for 2-DLA (thus for 3-DLA). Later, we show that Prediction can be solved much more efficiently for 1-DLA. In fact, we show that in that case the problem is NL-Complete. With respect to Realization, we show that restricted to 2-DLA the problem is in P, while in the 1-DLA case, the problem is in L.
Single-channel nonuniform sampling (SNS) is a Compressed Sensing (CS) approach that allows sub-Nyquist sampling of frequency sparse signals. The relatively simple architecture, comprising one wide band sampling channe...
详细信息
Single-channel nonuniform sampling (SNS) is a Compressed Sensing (CS) approach that allows sub-Nyquist sampling of frequency sparse signals. The relatively simple architecture, comprising one wide band sampling channel, makes it an attractive solution for applications such as signal analyzers and telecommunications. However, a high computational cost of the SNS signal reconstruction is an obstacle for real-time applications. This paper proposes to emulate multi-coset sampling (MCS) in SNS acquisition as a means to decrease the computational costs. Such an emulation introduces performance-complexity tradeoffs due to the difference of the SNS and MCS models. We investigate these tradeoffs with numerical simulations and theoretical assessments of the reconstruction complexity in multi-band signal scenarios. These scenarios include different numbers, different widths and positions of the frequency bands and different levels of noise in the signals. For the SNS reconstruction, we consider the accelerated iterative hard thresholding algorithm;for the MCS reconstruction, the multiple signal classification and focal underdetermined system solver algorithms are used. The proposed emulation reduces the computational complexity up to several orders of magnitude. For one of the scenarios, the reconstruction quality slightly decreases. For the other scenarios, the reconstruction quality is either preserved or improved. (C) 2016 Published by Elsevier B.V.
Place recognition and user positioning methods are becoming trending topics among the research community thanks to the need of providing cutting-edge solutions to enable innovative and efficient Location-Based Service...
详细信息
Place recognition and user positioning methods are becoming trending topics among the research community thanks to the need of providing cutting-edge solutions to enable innovative and efficient Location-Based Services (LBS) and applications. However, the mobile framework suffers from typical constraints on energy and computational capabilities due to the inherent characteristics of wireless mobile devices. For this reason, in order to be suitable for deploying in such framework, a place recognition algorithm should be thrifty in terms of resource consumption. In this paper we consider six different WiFi-based outdoor positioning approaches and we analytically derive an upper-bound for their computational burden in terms of number of FLoating-point OPerations (FLOPs).
Given a threshold automata network, as well as an updating scheme over its vertices, we study the computational complexity associated with the prediction of the future state of a vertex. More precisely, we analyze two...
详细信息
Given a threshold automata network, as well as an updating scheme over its vertices, we study the computational complexity associated with the prediction of the future state of a vertex. More precisely, we analyze two classes of local functions: the majority and the AND-OR rule (vertices take the AND or the OR logic functions over the state of its neighborhoods). Depending on the updating scheme, we determine the complexity class (NC, P, NP, PSPACE) where the prediction problem belongs. (C) 2014 Elsevier B.V. All rights reserved.
暂无评论