In the last several years the computational complexity of classical planning and HTN planning have been studied. But in both cases it is assumed that the planner has complete knowledge about the initial state. Recentl...
详细信息
ISBN:
(纸本)1558606130
In the last several years the computational complexity of classical planning and HTN planning have been studied. But in both cases it is assumed that the planner has complete knowledge about the initial state. Recently, there has been proposal to use 'sensing' actions to plan in presence of incompleteness. In this paper we study the complexity of planning in such cases. In our study we use the action description language A proposed in 1993 by M. Gelfond and V. Lifschitz and its extensions. The language A allows planning in the situations with complete information. It is known that, if we consider only plans of feasible (polynomial) length, the planning problem for such situations is NP-complete: even checking whether a given objective is attainable from a given initial state is NP-complete. In this paper, we show that the planning problem in presence of incompleteness is indeed harder: it belongs to the next level of complexity hierarchy (in precise terms, it is Sigma P-2-complete). To overcome the complexity of this problem, C. Baral and T. Son have proposed several approximations. We show that under certain conditions, one of these approximations - 0-approximation - makes the problem NP-complete (thus indeed reducing its complexity).
The multi-frontal direct solver is the state of the art for the direct solution of linear systems. This paper provides computational complexity and memory usage estimates for the application of the multi-frontal direc...
详细信息
The multi-frontal direct solver is the state of the art for the direct solution of linear systems. This paper provides computational complexity and memory usage estimates for the application of the multi-frontal direct solver algorithm on linear systems resulting from p finite elements. Specifically we provide the estimates for systems resulting from C-0 polynomial spaces spanned by B-splines. The structured grid and uniform polynomial order used in isogeometric meshes simplifies the analysis.
Petri net is a mathematical tool for discrete event systems. Workflow analysis is one of successful application of Petri net. DECLARE relation template is one of important properties to check validity of workflows. Th...
详细信息
ISBN:
(纸本)9781728110899
Petri net is a mathematical tool for discrete event systems. Workflow analysis is one of successful application of Petri net. DECLARE relation template is one of important properties to check validity of workflows. This paper studies computational complexity to decide whether the DECLARE relation templates between transitions A and B. The problems are shown to verified in determinstic polynomial time for sound acyclic free choice workflow nets. They are shown to be co-NP hard for sound acyclic non-free choice workflow nets.
The input to a constraint satisfaction problem (CSP) consists of a set of variables, each with a domain, and constraints between these variables formulated by relations over the appropriate domains;the question is if ...
详细信息
ISBN:
(纸本)9783540730002
The input to a constraint satisfaction problem (CSP) consists of a set of variables, each with a domain, and constraints between these variables formulated by relations over the appropriate domains;the question is if there is an assignment of values to the variables that satisfies all constraints. Different algorithmic tasks for CSPs (checking satisfiability, counting the number of solutions, enumerating all solutions) can be used to model many problems in areas such as computational logic, artificial intelligence, circuit design, etc. We will survey results on the complexity of these computational tasks as a function of properties of the allowed constraint relations. Particular attention is paid to the special case of Boolean constraint relations.
Active Queue Management (AQM) policies provide an early indication of incipient congestion to the source. In this paper, we propose a new AQM policy that predicts the instantaneous queue length at the next time instan...
详细信息
ISBN:
(纸本)9781424417339
Active Queue Management (AQM) policies provide an early indication of incipient congestion to the source. In this paper, we propose a new AQM policy that predicts the instantaneous queue length at the next time instant using adaptive filtering technique. To use this algorithm in fast routers, we have reduced its computational complexity. The proposed method uses a simple linear function as adaptive rule. We show that this adaptive congestion control method is able to control the oscillations in the instantaneous queue length. We compare the performance of our method with the other well-known AQM methods such as RED and PI which are also simulated by MATLAB. We also compare the computational complexity of these algorithms with each other.
Spectrum sculpting (SS) is a precoding scheme for sidelobe suppression of orthogonal frequency division multiplexing (OFDM) signals and can shape a spectrum with deep notches at chosen frequencies. However, the SS met...
详细信息
ISBN:
(纸本)9784885523014
Spectrum sculpting (SS) is a precoding scheme for sidelobe suppression of orthogonal frequency division multiplexing (OFDM) signals and can shape a spectrum with deep notches at chosen frequencies. However, the SS method will degrade the error rate as the number of notched frequencies increases. Orthogonal precoding of the SS has both a notched spectrum and an ideal error rate, but the computational complexity of the precoder matrix is very large. This paper proposes a matrix decomposition of the precoder matrix of the orthogonal precoding to reduce the computational complexity. Numerical experiments show that the proposed method can drastically reduce the computational complexity.
In combinatorial reconfiguration, the reconfiguration problems on a vertex subset (e.g., an independent set) are well investigated. In these problems, some tokens are placed on a subset of vertices of the graph, and t...
详细信息
ISBN:
(纸本)9783030895433;9783030895426
In combinatorial reconfiguration, the reconfiguration problems on a vertex subset (e.g., an independent set) are well investigated. In these problems, some tokens are placed on a subset of vertices of the graph, and there are three natural reconfiguration rules called "token sliding," "token jumping," and "token addition and removal". In the context of computational complexity of puzzles, the sliding block puzzles play an important role. Depending on the rules and set of pieces, the sliding block puzzles characterize the computational complexity classes including P, NP, and PSPACE. The sliding block puzzles correspond to the token sliding model in the context of combinatorial reconfiguration. On the other hand, a relatively new notion of jumping block puzzles is proposed in puzzle society. This is the counterpart to the token jumping model of the combinatorial reconfiguration problems in the context of block puzzles. We investigate several variants of jumping block puzzles and determine their computational complexities.
Providing students with suitably complex exercises is crucial to keeping them motivated and leading them to deeper understanding. Making such problems manually takes mathematics teachers' precious time which can o...
详细信息
ISBN:
(纸本)9781479984541
Providing students with suitably complex exercises is crucial to keeping them motivated and leading them to deeper understanding. Making such problems manually takes mathematics teachers' precious time which can otherwise be used to mentor students. Many software tools and services for automatic generation of math problems are found on the Web, but all of them provide only materials of high-school level or below. In addition, no standardized methods are provided to evaluate and control the computational complexity of generated problems. General concepts of complexity in various forms can be found in standard textbooks. The authors treat a different flavor of complexity, subjective complexity, where complexity is measured by the difficulty that learners feel. The authors proposed a new framework for evaluating computational complexity from learners' view, aiming to apply our framework to automatic generation of college math problems with controlled computational complexity. To prove the effectiveness of the new concept of complexity from learners' perspective, we developed some automatic generation tools based on our framework. In this paper, we will present one of the tools that supports automatic generation of eigenvalue problems. Controlling the complexity of eigenvalue problems involves restricting the number of calculation steps, the heights of the involved rationals, and the algebraic number fields appearing in the model solution of the problem. The small-scale experiments showed the relevance of our framework. Our system makes a path to strict quantitative control on various complexity from the learners' view. Future work includes the application of our methods to other areas such as differential equations, number theory and so on. We also should prove that this system has a positive effect on the engineering education at college level. Therefore, demonstration experiments in classroom will be scheduled in the next step of our research.
This article contains an overview of the literature concerning the computational complexity of Metropolis-Hastings based MCMC methods for sampling probability measures on R-d, when the dimension d is large. The materi...
详细信息
ISBN:
(纸本)9783642041068
This article contains an overview of the literature concerning the computational complexity of Metropolis-Hastings based MCMC methods for sampling probability measures on R-d, when the dimension d is large. The material is structured in three parts addressing, in turn, the following questions: (i) what are sensible assumptions to make on the family of probability measures indexed by d? (ii) what is known concerning computational complexity for Metropolis-Hastings methods applied to these families? (iii) what remains open in this area?
Semi-stable semantics offer a further extension based formalism by which the concept of "collection of justified arguments" in abstract argumentation frameworks may be described. In contrast to the better kn...
详细信息
ISBN:
(纸本)9783540878025
Semi-stable semantics offer a further extension based formalism by which the concept of "collection of justified arguments" in abstract argumentation frameworks may be described. In contrast to the better known stable semantics, one advantage of semi-stability is that any finite argumentation framework always has at least one semi-stable extension. Although there has been some development of the formal logical theory of semi-stable semantics so that several computational properties of these extensions have been identified, with the exception of some algorithmic studies, more detailed investigation of computational complexity issues has been neglected. Our purpose in this article is to present a number of results on the complexity of some natural decision questions for semi-stable semantics.
暂无评论