搜索结果: 1-15 共查到“数学 Complexity”相关记录69条 . 查询时间(0.156 秒)
Academy of Mathematics and Systems Science, CAS Colloquia & Seminars：The complexity of computing Markov perfect equilibrium in general-sum stochastic games
一般 随机博弈 马尔可夫完美均衡 计算复杂性
2023/5/12
Similar to the role of Markov decision processes in reinforcement learning, Markov games (also known as stochastic games) form the basis for the study of multi-agent reinforcement learning and sequenc...
On the computability-theoretic complexity of trivial, strongly minimal models
computability-theoretic strongly minimal models
2015/9/28
We show the existence of a trivial, strongly minimal (and thus
uncountably categorical) theory for which the prime model is computable and
each of the other countable models computes 0
00. This res...
Borel complexity of complete, first order theories(status report)
first order theories status report
2015/9/25
Borel complexity of complete, first order theories(status report).
Karp complexity and classes with the independence property
Karp complexity independence property
2015/9/25
A class K of structures is controlled if for all cardinals
λ, the relation of L∞,λ-equivalence partitions K into a set of
equivalence classes (as opposed to a proper class). We prove that
no pseudo...
Filter design with low complexity coefficients
Heuristic design low complexity coefficient filters with nonzero number the filter coefficients
2015/8/10
We introduce a heuristic for designing filters that have low complexity coefficients, as measured by the total number of nonzeros digits in the binary or canonic signed digit (CSD) representations of ...
Simple Bounds for Recovering Low-complexity Models
`1-norm minimization nuclear-norm minimization block-sparsity duality random matrices
2015/6/17
This note presents a unified analysis of the recovery of simple objects from random linear measurements. When the linear functionals are Gaussian, we show that an s-sparse vector in Rn can be efficien...
On the Complexity of 2D Discrete Fixed Point Problem
Complexity 2D Discrete Fixed Point Problem
2012/12/3
While the 3-dimensional analogue of Sperner’s problem in the plane was known to be complete in class PPAD, the complexity of 2D-SPERNER itself is not known to be PPAD-complete or not. In this paper, w...
Topological complexity of motion planning in projective product spaces
Topological complexity product projective spaces Euclidean immersions of manifolds generalized axial maps
2012/6/14
We study Farber's topological complexity (TC) of Davis' projective product spaces (PPS's). We show that, in many non-trivial instances, the TC of PPS's coming from at least two sphere factors is (much...
Absolutely symmetric trees and complexity of natural number
Absolutely symmetric trees complexity of natural number Combinatorics
2012/5/24
We consider the rooted trees which not have isomorphic representation and introduce a conception of complexity a natural number also. The connection between quantity such trees with $n$ edges and a co...
Equivariant topological complexity
Equivariant LS-category equivariant sectional category equivariant topological complexity
2012/5/9
We define and study an equivariant version of Farber's topological complexity for spaces with a given compact group action. This is a special case of the equivariant sectional category of an equivaria...
A cooperative conjugate gradient method for linear systems permitting multithread implementation of low complexity
cooperative conjugate gradient method linear systems multithread implementation low complexity Numerical Analysis
2012/4/17
This paper proposes a generalization of the conjugate gradient (CG) method used to solve the equation $Ax=b$ for a symmetric positive definite matrix $A$ of large size $n$. The generalization consists...
On finite decomposition complexity of Thompson's group F
Thompson's group F Finite decomposition complexity Word-metric Exact metric spaces Reduced forest diagram
2011/10/20
Finite decomposition complexity m(FDC) is a large scale property of a metricspace. It generalizes finite asymptoticdimension and applies to a wide class of groups. To make the property quantitative, a...
The Streaming Complexity of Cycle Counting, Sorting By Reversals, and Other Problems
Streaming Complexity Cycle Counting,
2012/12/3
In this paper we introduce a new technique for proving streaming lower bounds (and one-way communication lower bounds), by reductions from a problem called the Boolean Hidden Hypermatching problem (BH...
We study the complexity of testing if two given matroids are isomorphic. The problem is easily seen to be in p 2 . In the case of linear matroids, which are
represented over polynomially growing fie...
Average-Case Separation in Proof Complexity:Short Propositional Refutations for Random 3CNF Formulas
Average-Case Short Propositional Random 3CNF Formulas
2012/12/4
Separating different propositional proof systems梩hat is, demonstrating that one proof system cannot efficiently simulate another proof system梚s one of the main goals of proof complexity. Nevertheless,...