搜索结果: 1-9 共查到“数理逻辑与数学基础 Complexity”相关记录9条 . 查询时间(0.581 秒)
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).
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...
A Computational Complexity-Theoretic Elaboration of Weak Truth-Table Reducibility
algorithmic information theory algorithmic randomness weak truth-table reducibility
2011/9/14
Abstract: The notion of weak truth-table reducibility plays an important role in recursion theory. In this paper, we introduce an elaboration of this notion, where a computable bound on the use functi...
Lower Bounds for the Determinantal Complexity of Explicit Low Degree Polynomials
Computational complexity Arithmetic circuits Determinant versus permanent Elementary symmetric polynomial
2012/12/3
The determinantal complexity of a polynomial f (x1, x2, . . . , xn) is the minimum m such that f = detm(L(x1, x2, . . . , xn)), where L(x1, x2, . . . , xn) is a matrix whose entries are affine forms i...
In their position paper entitled "Towards a new, complexity science of learning and education", Jorg et al. (2007) argue that educational research is in crisis. In their opinion, the transdisciplinary...
The Approximation Complexity of Win-Lose Games
The Approximation Complexity Win-Lose Games
2012/11/29
We further our algorithmic and structural understanding of Nash equilibria.
Computing Nash Equilibria: Approximation and Smoothed Complexity
Computing Nash Equilibria Approximation Smoothed Complexity
2012/11/29
We advance significantly beyond the recent progress on the algorithmic complexity of Nash equilibria by solving two major open problems in the approximation of Nash equilibria and in the smoothed anal...
We prove that the problem of finding a Nash equilibrium in a two-player game is PPAD-complete.