Search results for "Complexity theory"
showing 9 items of 139 documents
Multi-label Classification Using Stacked Hierarchical Dirichlet Processes with Reduced Sampling Complexity
2018
Nonparametric topic models based on hierarchical Dirichlet processes (HDPs) allow for the number of topics to be automatically discovered from the data. The computational complexity of standard Gibbs sampling techniques for model training is linear in the number of topics. Recently, it was reduced to be linear in the number of topics per word using a technique called alias sampling combined with Metropolis Hastings (MH) sampling. We propose a different proposal distribution for the MH step based on the observation that distributions on the upper hierarchy level change slower than the document-specific distributions at the lower level. This reduces the sampling complexity, making it linear i…
Heterogeneity in family firms: contextualising the adoption of family governance mechanisms
2020
PurposeThis research is aimed to better understand what characteristics of family firms create a context in which family governance systems are more frequently adopted.Design/methodology/approachWe analyse a sample of 490 Spanish family businesses using cluster analysis, and we identify four different types of family businesses whose characteristics are associated to the adoption of different family governance systems, i.e. family councils and family protocols. The comparison between clusters of the baseline parameters was performed using one-way analysis of variance (ANOVA) for parametric variables, the χ2 test for parametric variables and Kruskal-Wallis for nonparametric variables. By con…
Chromatic sums for colorings avoiding monochromatic subgraphs
2015
Abstract Given graphs G and H, a vertex coloring c : V ( G ) → N is an H-free coloring of G if no color class contains a subgraph isomorphic to H. The H-free chromatic number of G, χ ( H , G ) , is the minimum number of colors in an H-free coloring of G. The H-free chromatic sum of G , Σ ( H , G ) , is the minimum value achieved by summing the vertex colors of each H-free coloring of G. We provide a general bound for Σ ( H , G ) , discuss the computational complexity of finding this parameter for different choices of H, and prove an exact formulas for some graphs G. For every integer k and for every graph H, we construct families of graphs, G k with the property that k more colors than χ ( …
Some Computational Aspects of DISTANCE-SAT
2007
In many AI fields, one must face the problem of finding a solution that is as close as possible to a given configuration. This paper addresses this problem in a propositional framework. We introduce the decision problem distance-sat, which consists in determining whether a propositional formula admits a model that disagrees with a given partial interpretation on at most d variables. The complexity of distance-sat and of several restrictions of it are identified. Two algorithms based on the well-known Davis/Logemann/Loveland search procedure for the satisfiability problem sat are presented so as to solve distance-sat for CNF formulas. Their computational behaviors are compared with the ones …
Inverse Tone Mapping Based upon Retina Response
2014
International audience; The development of high dynamic range (HDR) display arouses the research of inverse tone mapping methods, which expand dynamic range of the low dynamic range (LDR) image to match that of HDR monitor. This paper proposed a novel physiological approach, which could avoid artifacts occurred in most existing algorithms. Inspired by the property of the human visual system (HVS), this dynamic range expansion scheme performs with a low computational complexity and a limited number of parameters and obtains high-quality HDR results. Comparisons with three recent algorithms in the literature also show that the proposed method reveals more important image details and produces …
COMPLIANCE PROGRAM IN LATVIAS’ BANKING SECTOR: THE RESULTS OF A SURVEY
2012
Regulators more than ever believe an efficient compliance function is a prerequisite for good corporate governance that should restore trust, integrity, and responsibility in the banks, findings in academic research has confirmed mentioned above in many countries. Compliance is key facet of governance because it shows how actually bank meets corporate responsibilities. The new guidelines in September 2011 had been issued by European Banking Authority with more attention to the compliance function. Compliance is very complex function and covers different areas: Anti-money laundering, investment protection, consumer protection, data protection and etc. Compliance complexity arises from severa…
A Neuro-Ethological Approach for the TSP: Changing Metaphors in Connectionist Models.
1994
Biological systems often offer solutions to difficult problems which are not only original but also efficient. Connectionist models have been inspired by neural systems and successfully applied to the formulation of algorithms for solving complex problems such as the travelling salesman problem. In this paper we extend the connectionist metaphor to include an ethological account of how problems similar to the travelling salesman problem are solved by real living systems. A model is presented in which a population of neural networks with simple sensory-motor systems evolve genetically in simulated environments which represent the problem instances to be solved. Preliminary results are discu…
Adding Transitivity and Counting to the Fluted Fragment
2023
We study the impact of adding both counting quantifiers and a single transitive relation to the fluted fragment - a fragment of first-order logic originating in the work of W.V.O. Quine. The resulting formalism can be viewed as a multi-variable, non-guarded extension of certain systems of description logic featuring number restrictions and transitive roles, but lacking role-inverses. We establish the finite model property for our logic, and show that the satisfiability problem for its k-variable sub-fragment is in (k+1)-NExpTime. We also derive ExpSpace-hardness of the satisfiability problem for the two-variable, fluted fragment with one transitive relation (but without counting quantifiers…
The Syllogistic with Unity
2011
We extend the language of the classical syllogisms with the sentence-forms “At most 1 p is a q” and “More than 1 p is a q”. We show that the resulting logic does not admit a finite set of syllogism-like rules whose associated derivation relation is sound and complete, even when reductio ad absurdum is allowed.