NP-complete problems are particularly hard to solve. Unless P=NP, any algorithm solving an NP-complete problem takes exponential time in the worst case. The intrinsic difficulty of NP-complete problems when we try to optimally solve them with compute
18 June 2014 in IEEE Transactions on Software Engineering
In this paper we develop a general framework to reason about testing. The difficulty of testing is assessed in terms of the amount of tests that must be applied to determine whether the system is correct or not. Based on this criterion, five testability classes are presented and related. We also explore conditions that enable and disable finite testability, and their relation to testing hypotheses is studied. We measure how far incomplete test suites are from being complete, which allows us to compare and select better incomplete test suites. The complexity of finding that measure, as well as the complexity of finding minimum complete test suites, is identified. Furthermore, we address the reduction of testing problems to each other, that is, we study how the problem of finding test suites to test systems of some kind can be reduced to the problem of finding test suites for another kind of systems. This enables to export testing methods. In order to illustrate how general notions are applied to specific cases, many typical examples from the formal testing techniques domain are presented.
River formation dynamics (RFD) is an heuristic optimization algorithm based on copying how water forms rivers by eroding the ground and depositing sediments. After drops transform the landscape by increasing/decreasing the altitude of places, solutions are given in the form of paths of decreasing altitudes. Decreasing gradients are constructed, and these gradients are followed by subsequent drops to compose new gradients and reinforce the best ones. We apply this method to solve dynamic TSP. We show that the gradient orientation of RFD makes it specially suitable for solving this problem, and we compare our results with those given by ant colony optimization (ACO).
HighlightsFormally defining how to select product features to maximize the number of customers.Proving the bad approximability (Poly-APX-completeness) of the one-step variant.Heuristically solving these problems by using GA, PSO and minimax algorithms.Developing a case study based on real preferences obtained from political polls.Proving the intractability (EXPTIME- and PSPACE-completeness) of its game variants. We formalize and analyze the computational complexity of three problems which are at the keystone of any marketing management process. Given the preferences of customers over the attribute values we may assign to our product (i.e. its possible features), the attribute values of products sold by our competitors, and which attribute values are available to each producer (due to e.g. technological limitations, legal issues, or availability of resources), we consider the following problems: (a) select the attributes of our product in such a way that the number of customers is maximized; (b) find out whether there is a feasible strategy guaranteeing that, at some point in the future before some deadline, we will reach a given average number of customers during some period of time; and (c) the same question as (b), though the number of steps before the deadline is restricted to be, at most, the number of attributes. We prove that these problems are Poly-APX-complete, EXPTIME-complete, and PSPACE-complete, respectively. After presenting these theoretical properties, heuristic methods based on genetic, swarm and minimax algorithms are proposed to suboptimally solve these problems. We report experimental results where these methods are applied to solve some artificially-designed problem instances, and next we present a case study, based on real data, where these algorithms are applied to a particular kind of product: we automatically design the political platform of a political party to maximize its numbers of votes in an election (problem (a)) and its number of supporters along time (problems (b) and (c)). The problem instances solved in this case study are constructed from publicly released polls on political tendencies in Spain.